题目

一颗\(n\)个节点的树，每个点有一个权值\(a_i\)

询问树上连通块权值之和对 \(m\) 取模为$ x $ 的方案数

答案对\(950009857\) 取模，满足\(m | 950009857\)

空间\(32 \ M\)

题解

• 考虑\(F_i(x)\)为i为根的连通块的生成函数，\(G(x)\)为答案的生成函数

  \[ \begin{align} F_i(x) \ = \ (\prod F_{son(i)}+1)x^{a_i} \\ G(x) \ = \ \sum F_i(x) \\ \end{align} \]

• 一个比较naive的想法就是每次都dft,idft之后手动将系数取模，但其实没有必要

• 可以直接对每个点求出dft，O(nm)求出点乘后的结果，最后做一次idft之后的到的答案就是循环卷积

  注意每个点的形式是\(x^a_i\)，预处理单位根的次幂可以直接得到dft

• 对于空间，重链剖分之后把一个点的数组直接传给重儿子，一个点dfs完之后回收一下

  最大引用数组就是一条链上的轻链个数

• 时间复杂度:\(O(nm + m \ log \ m)\) ; 空间复杂度:\(O(m \ log \ n)\)

• 为什么idft之后的结果是循环卷积呢？

  \[ \begin{align} &考虑一个次数界为n的式子\{A_i\}在m次下的点值表达：\{dft(A)_i\}\\ &设\{B_i\}为idft之后的结果\\ &B_r = \sum_{j=0}^{m-1}\frac{1}{m}dft(A)_j \omega_m^{-jr}\\ &= \sum_{j=0}^{m-1}\sum_{k=0}^{n-1}\frac{1}{m}A_k \omega_m^{j(k-r)}\\ &= \sum_{k=0}^{n-1}A_k (\sum_{j=0}^{m-1}\frac{1}{m}\omega_m^{j(k-r)})\\ &运用求和引理，B_r = \sum_{j=0}^{n-1}A_k[m|j-r]\\ &即m次意义下的循环卷积 \end{align} \]

Code

#include
    
     #define mod 950009857using namespace std;const int N=1<<18,M=14,R=7;int n,m,a[N],o=1,hd[N],sz[N],sn[N],f[M][N],q[M],head,tail,now,id[N],g[N];int t1[N],t2[N],len,L,rev[N],w[N],W[N];struct Edge{int v,nt;}E[N<<1];void adde(int u,int v){    E[o]=(Edge){v,hd[u]};hd[u]=o++;    E[o]=(Edge){u,hd[v]};hd[v]=o++;}void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}void dfsA(int u,int fa){    sz[u]=1;    for(int i=hd[u];i;i=E[i].nt){        int v=E[i].v;        if(v==fa)continue;        dfsA(v,u);        sz[u]+=sz[v];        if(sz[v]>sz[sn[u]])sn[u]=v;    }}int get(){    if(head==tail)q[tail++]=++now;    if(tail==21)tail=0;    int re=q[head++],*F=f[re];    for(int i=0;i
     
      =m)t-=m;    }    for(int i=hd[u];i;i=E[i].nt){        int v=E[i].v;        if(v==fa||v==sn[u])continue;        dfsB(v,u);        int *G=f[id[v]];        for(int j=0;j
      
       >=1,x=1ll*x*x%mod)        if(y&1)re=1ll*re*x%mod;    return re;}void ntt(int*A,int F){    for(int i=0;i
       
        
         >1]>>1)|((i&1)<<(L-1));    for(int i=0;i<=(m-1)<<1;++i){        W[i]=w[1ll*i*(i-1)/2%m];        t2[i]=pw(W[i],mod-2);    }    for(int i=0;i