彩燈晚會：

\(n\) 點 \(m\) 邊 \(k\) 種顏色，給每個點染色。
\(cnt_i\)：第 \(i\) 種顏色長度為 \(l\) 的鏈的數量。其中 \(l\) 為題目給的一個常量。
求 \(\sum_{染色方案}\sum_{i=1}^k cnt_i^2\) 的和。

一

\(\sum_{染色方案}cnt_i\) 值都一樣，欽定 \(pos\) 作為代表顏色，那么：
\(\sum_{染色方案}\sum_{i=1}^k cnt_i^2=k×\sum_{染色方案}cnt_{pos}^2\)

二

如果不解決 \(cnt_{pos}^2\)，那么我們不得不枚舉染色方案，所以考慮解決 \(cnt_{pos}^2\)。
思考圖論意義，\(cnt_{pos}^2=(1+1+…+1+1)×(1+1+…+1+1)\)
手玩可得：\(cnt_{pos}^2\) 為選擇兩個顏色為 pos 長度為 l 的鏈的方案數。

已經到可以 DP 的程度了。
\(f_{u,len1,len2,p}\)：\(u\) 作為第 \(p\) 個重合點，鏈一長度為 \(len1\)，鏈二長度為 \(len2\) 的方案數。
這時候發現轉移很難，因為為了維護 DP 含義，我們不得不使兩個鏈到下一個重合點前沒有重合點。
用二項式反演把 DP 含義從“恰好”改為“欽定”就好了！

• 具體的（\(F(i)\) 表示“欽定”，\(G(i)\) 表示“恰好”：
  \(F(i)=\sum_{i=1}^n k×f_{u,l,l,i}×k^{n-2l+i}\)（第一個 \(k\) 是 \(pos\) 的值域）
  \(G(i)=\sum_{j=i}^l (-1)^{j-i} \binom{j}{i} F(j)\)

\(dis_{u,v,len}\)：從 \(u\) 到 \(v\) 長度為 \(len\) 的路徑數。
\(st_{u,len}\)：\(u\) 開頭長度為 \(len\) 的路徑條數。
\(ed_{u,len}\)：\(u\) 結尾長度為 \(len\) 的路徑條數。

\(O(n^3l+n^2l^5)\)，其中 \(n^2l^5\) 中的一個 \(n\) 跑不滿（DAG）導致 \([76,84]\) 分，拿上直接變人上人。

三

trick：分步枚舉

• 具體的：
  \(cab_{u,len1,len2,p}\)：當前 \(len1\) 轉移完了的 \(f\) 數組。
  \(f_{u,len1,len2,p}\)：完整轉移后的 \(f\) 數組。
  先枚舉 \(len1\) 用 \(f_{u,len1,len2,p}\) 更新 \(cab_{v,len1+k,len2,p+1}\)。
  再枚舉 \(len2\) 用 \(cab_{u,len1,len2,p}\) 更新 \(f_{v,len1,len2+k,p+1}\)。

\(O(n^3l+n^2l^4)\)——\([84,92]\) 分，考場知足分。

四

宇宙射線：把計算公式代入二項式反演的式子里化簡。

\(H(i)=\sum_{i=1}^n f_{u,l,l,i}\)
\(F(i)=k^{n-2l+i+1}H(i)\)（第一個 \(k\) 是 \(pos\) 的值域）
\(G(i)=\sum_{j=i}^l (-1)^{j-i} \binom{j}{i} F(j)\)

trick：\((k-1)^j\) 和 \(H(j)\) 的次數一樣，可以直接把 \((k-1)\) 下發到 \(H(j)→H(j+1)\) 的轉移，這時無須記錄重合點個數了，直接一起計算就行了。

\(O(n^3l+n^2l^3)\)——\(100\) 分，卡常就不說了。

美碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
int id,n,k,l,m; 
struct bbb {int v,w;} ;
const int QAQ=310,mo=998244353,ovo=22;
int idfn[QAQ],rd[QAQ],cab[QAQ][ovo][ovo],ed[QAQ][ovo],st[QAQ][ovo];
int f[QAQ][ovo][ovo],dis[QAQ][QAQ][ovo];
vector<bbb> dian[QAQ];
queue<int> dui;
int cnt;
__int128 ans;
#define jia(x,y) x=(x+y)%mo
int ksm(int x,int k)
{
	int da=1;
	for(;k;k>>=1,x=x*x%mo) if(k&1) da=da*x%mo;
	return da;
}
void write(__int128 ans)
{
	if(ans==0) return ;
	write(ans/10);
	putchar(ans%10+'0');
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>id>>n>>k>>l>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dian[u].push_back({v,w});
		rd[v]++;
	}
	for(int i=1;i<=n;i++) if(rd[i]==0) dui.push(i);
	while(!dui.empty())
	{
		int x=dui.front();dui.pop();
		++cnt,idfn[cnt]=x;
		for(bbb nw:dian[x])
		{
			rd[nw.v]--;
			if(rd[nw.v]==0) dui.push(nw.v);
		}
	}
	for(int i1=1;i1<=n;i1++)
	{
		int i=idfn[i1];
		dis[i][i][1]=1;
		for(int i2=i1;i2<=n;i2++)
			for(int len=1;len<l;len++)
			{
				int j=idfn[i2];
				for(bbb nw:dian[j])
					jia(dis[i][nw.v][len+1],dis[i][j][len]*nw.w);
			}
	}
	for(int i=1;i<=n;i++)
		for(int k=1;k<=n;k++)
			for(int j=1;j<=l;j++)
				jia(st[i][j],dis[i][k][j]),
				jia(ed[i][j],dis[k][i][j]);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans+=dis[i][j][l];
	ans%=mo;
	ans=ans*ans%mo;
	
	for(int i=1;i<=n;i++)
	{
		int u=idfn[i];
		for(int o1=1;o1<=l;o1++)
			for(int o2=1;o2<=l;o2++)
				jia(f[u][o1][o2],ed[u][o1]*ed[u][o2]%mo*(k-1));
		for(int k=1;k<=n;k++)
			for(int i=1;i<=l;i++)
				for(int j=1;j<=l;j++)
					cab[k][i][j]=0;
		for(int i2=i;i2<=n;i2++)
			for(int o1=1;o1<=l;o1++)
				for(int o2=1;o2<=l;o2++)
				{
					int v=idfn[i2];
					for(int c=1;c<=l-o1;c++)
						jia(cab[v][o1+c][o2],f[u][o1][o2]*dis[u][v][c+1]);
				}
		for(int i2=i;i2<=n;i2++)
			for(int o1=1;o1<=l;o1++)
				for(int o2=1;o2<=l;o2++)
				{
					int v=idfn[i2];
					for(int c=1;c<=l-o2;c++)
						jia(f[v][o1][o2+c],cab[v][o1][o2]*dis[u][v][c+1]%mo*(k-1));
				}
	}
	for(int i=1;i<=n;i++)
		for(int o1=1;o1<=l;o1++)
			for(int o2=1;o2<=l;o2++)
				ans+=f[i][o1][o2]*st[i][l-o1+1]%mo*st[i][l-o2+1]%mo;
	ans%=mo;
	if(n-2*l+1>=0) ans=ans*ksm(k,n-2*l+1)%mo;
	else ans=ans*ksm(ksm(k,mo-2),-(n-2*l+1))%mo;
	if(ans==0) cout<<"0";
	else write(ans);
	return 0;
}