Solved：12/14
Rank：5/1k+
Rank（vp）：49/2k+
Penalty：1619
Dirt：45%
前 10 个题都比较简单/套路。
L
做法很好想。但是……
因为不会写启发式合并卡了 40min，警钟长鸣！
int sum[N];
map<int,int> col[N];
int sz[N];
ll now[N],ans[N];
void mrg(int x,int y){
x=find(x),y=find(y);
if(sz[x]<sz[y])swap(x,y),now[y]=now[x];
sz[x]+=sz[y],f[y]=x;
for(auto& [z,w]:col[y]){
int& t=col[x][z];
now[x]-=1ll*t*(sum[z]-t);
t+=w;
now[x]+=1ll*t*(sum[z]-t);
}
}
void dfs(int u,int f,int i){
sz[u]=1,++col[u][c[u]];
now[u]=sum[c[u]]-1;
for(auto [v,j]:e[u])if(v^f)
dfs(v,u,j),mrg(u,v);
ans[i]=now[find(u)];
}
K
\[f_{n,k}=\sum_if_{n-d_i,k-p_i}, n\leq 10^9, d_i\leq 10, k\leq 400 \]这个\(d\)的范围很想矩乘，如果直接把400全压进向量里就是4000维，肯定T。
令\(f_n(x) = \sum_{k=0}^K f_{n,k}x^k\)，则转移方程变为
\[f_n(x) = \sum_i x^{p_i}f_{n-d_i}(x) \]且 \(f_0(x)=1\)。这样就变成多项式为元素的矩阵乘法了。
复杂度\(O(d^3K^2\log n)\)
也可以直接做 4000 项的线性递推。复杂度少一个 d。
标签：Brazil,10,2024.10,Contest,int,sum,leq,复杂度 From： https://www.cnblogs.com/EssentialSingularity/p/18514566