题解：P11292 【MX-S6-T4】「KDOI-11」彩灯晚会
yangzichen1203
·
·
题解
较为困难的数数题。（是我太菜了）
形式化题面
给定一张有重边的 DAG，有 k 种颜色，你要对每个点染色。
给定常数 L，对于一种染色方案，定义长度为 p 的颜色为 q 的链表示一个点数为 p 的链，满足链上点的颜色均为 q。
设恰好有 cnt_i 个颜色为 i 的长度为 L 的同色链，则定义这个方案的权值为所有 i 的 cnt_i 的平方和，求所有染色方案的权值和。
题解
:::info[Hint 1]
首先有一个 trick（我没想到），就是单条链的 \sum cnt^2 可以转换为任意选两条链（可重）的总方案数。
:::
:::success[Part 1]
考虑到两条链可能有交叉，所以设两条链交叉点数量为 x，则方案数为 k^{n-2L+x+1}。
考虑 DP 求解，我们要求两条长度为 L 的链，其恰好在 x 个位置重合。
:::
:::info[Hint 2]
由于“恰好”不好做，我们改成“至少”，然后用二项式反演搞回去。
:::
:::success[Part 2]
设 \Large f_{u,x,l_1,l_2} 表示当前在 u 点重合，已经钦定重合了 x 次，两条链的长度分别为 l_1 和 l_2 的方案数。则转移就是钦定两条链在一个新的 v 点重合，使用长度为 t_1 的路径更新 l_1，使用长度为 t_2 的路径更新 l_2。我们预处理出每两个点在某一距离的路径数即可 O(1) 转移。
写一下转移方程式：
\Large f_{u,x,l_1,l_2}\to f_{v,x+1,l_1+t_1,l_2+t_2}
答案：
ans=\sum_{i=0}^{L}k^{n-2L+i+1}\sum_{j=i}^{L}(-1)^{j-i}\binom{j}{i}f_{*,j,*,*}
时间复杂度：预处理 O(n^3 L)，转移 O(n^2 L^5)。
空间复杂度：预处理 O(n^2 L)，状态 O(n L^3)。
显然还需要优化复杂度。
:::
:::success[Part 3]
显然还需要优化复杂度。
:::
:::success[Part 4]
考虑减少状态数来优化，尝试去掉第二维，把二项式反演的贡献在计算过程中算好。
$$ans=\sum_{i=0}^{L}k^{n-2L+i+1}\sum_{j=i}^{L}(-1)^{j-i}\binom{j}{i}f_{*,j,*,*}$$
$$=k^{n-2L+1}\sum_{i=0}^{L}k^{i}\sum_{j=i}^{L}(-1)^{j-i}\binom{j}{i}f_{*,j,*,*}$$
$$=k^{n-2L+1}\sum_{j=0}^{L}f_{*,j,*,*}\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}k^{i}$$
$$=k^{n-2L+1}\sum_{j=0}^{L}f_{*,j,*,*}(k-1)^{j}$$
我们在每次第二维需要加 $1$ 时乘上 $k-1$ 的贡献，即可把第二维省掉，时间复杂度优化为 $O(n^2 L^3)$，再加上适量卡常即可通过本题。
时间复杂度：$O(n^3 L+n^2 L^3)$。
空间复杂度：$O(n^2 L+nL^2)$。
:::
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 305
#define MAXL 25
#define Mod 998244353
inline int md(int x){
return x>=Mod?x-Mod:x;
}
int Pow(int x,int y){
if(y<0) y+=Mod-1;
int ans=1;
while(y){
if(y&1){
ans=1ll*ans*x%Mod;
}
x=1ll*x*x%Mod;
y>>=1;
}
return ans;
}
int C,n,k,L,m;
vector<pair<int,int>> e[MAXN];
int in[MAXN],id[MAXN],tot=0;
int f[MAXN][MAXN][MAXL],st[MAXN][MAXL],ed[MAXN][MAXL];
int g[MAXN][MAXL][MAXL],h[MAXN][MAXL][MAXL];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>C>>n>>k>>L>>m;
For(i,1,m){
int u,v,c;
cin>>u>>v>>c;
e[u].push_back({v,c});
in[v]++;
}
queue<int> q;
For(i,1,n){
if(!in[i]){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
id[++tot]=u;
for(auto [v,w]:e[u]){
in[v]--;
if(in[v]==0){
q.push(v);
}
}
}
For(i,1,n){
int u=id[i];
f[u][u][1]=1;
For(j,i,n){
int v=id[j];
For(k,1,L-1){
for(auto [w,c]:e[v]){
f[u][w][k+1]=md(f[u][w][k+1]+1ll*f[u][v][k]*c%Mod);
}
}
}
}
For(i,1,n){
For(j,1,n){
For(k,1,L){
st[i][k]=md(st[i][k]+f[i][j][k]);
ed[j][k]=md(ed[j][k]+f[i][j][k]);
}
}
}
int ans=0;
For(i,1,n){
For(j,1,n){
ans=md(ans+f[i][j][L]);
}
}
ans=1ll*ans*ans%Mod;
For(i,1,n){
int u=id[i];
For(l1,1,L){
For(l2,1,L){
g[u][l1][l2]=md(g[u][l1][l2]+1ll*ed[u][l1]*ed[u][l2]%Mod*(k-1)%Mod);
}
}
memset(h,0,sizeof(h));
For(j,i+1,n){
int v=id[j];
For(l1,1,L){
For(l2,1,L){
For(t1,1,L-l1){
h[v][l1+t1][l2]=md(h[v][l1+t1][l2]+1ll*g[u][l1][l2]*f[u][v][t1+1]%Mod);
}
}
}
}
For(j,i+1,n){
int v=id[j];
For(l1,1,L){
For(l2,1,L){
For(t2,1,L-l2){
g[v][l1][l2+t2]=md(g[v][l1][l2+t2]+1ll*h[v][l1][l2]*f[u][v][t2+1]%Mod*(k-1)%Mod);
}
}
}
}
}
For(i,1,n){
int u=id[i];
For(l1,1,L){
For(l2,1,L){
ans=md(ans+1ll*g[u][l1][l2]*st[u][L-l1+1]%Mod*st[u][L-l2+1]%Mod);
}
}
}
ans=1ll*ans*Pow(k,n-L*2+1)%Mod;
cout<<ans<<endl;
return 0;
}
```
:::