【UOJ#50】【UR #3】链式反应（分治FFT，动态规划）

题面

题解

首先把题目意思捋一捋，大概就是有\(n\)个节点的一棵树，父亲的编号大于儿子。

满足一个点的儿子有\(2+c\)个，其中\(c\in A\)，且\(c\)个儿子是叶子，另外\(2\)个存在子树，且两种点的链接的边是不同的，求方案数。

那么就考虑一个暴力\(dp\)，设\(f[i]\)表示有\(i\)个节点的树的个数。

那么枚举它两个有子树的子树大小，然后把编号给取出来，得到：

\[f[i]=\frac{1}{2}\sum_{j}\sum_{k} {i-1\choose j}{i-1-j\choose k}f[j]f[k]\]

其中存在限制，也就是\(i-1-j-k\in A\)，要乘\(\frac{1}{2}\)是因为这两个子树选择的时候存在先后关系，所以同一棵子树可能会被计算两次。

这样子我们就可以做\(O(n^3)\)了。

然后把式子给拆一下：

\[{i-1\choose j}{i-1-j\choose k}=\frac{(i-1)!}{j!k!(i-1-j-k)!}\]

之和\(i,j,k\)相关的可以直接和\(f[i],f[j],f[k]\)丢到一起，剩下的只和\(i/j+k\)相关。

然后预处理\(g[i]=\sum_j \frac{f[j]}{j!}\frac{f[i-j]}{(i-j)!}\)。

那么

\[\frac{2f[i]}{(i-1)!}=\sum_{p=j+k}g[p]*[i-1-p\in A]\]

这样子就可以做到\(O(n^2)\)了。

进一步发现，\(g\)和\(\frac{2f}{(i-1)!}\)都是卷积的形式，所以可以直接分治\(FFT\)求解做到\(O(nlog^2)\)。

然而这里有细节、、、乱搞会挂。

注意到分治\(FFT\)的过程是\([l,mid]\rightarrow [mid+1,r]\)，而\(g\)数组在求解的时候是\(f\)卷上\(f\)，这样子会导致乘的数组的范围是\([0,r-l]\)，可能存在一部分值没有被计算过。

而这个值具有对称性，所以我们强制\(j<k\)的时候才贡献\(2f[j]*f[k]\)。

也就是如果\(i<l\)的时候，数组里丢进去的是\(2f[i]\)，当\(l\le i\le mid\)的时候丢\(f[i]\)，否则丢\(0\)进去。

然后两个\(log\)就能过了。

然而这题看起来有更加优秀的做法，但是窝太菜了就不管了。

#include
    
     #include
     
      #include
      
       using namespace std;#define MOD 998244353#define MAX 840000int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}int r[MAX],W[MAX];void NTT(int *P,int opt,int len){    int N,l=0;for(N=1;N
       
        <<=1)++l;    for(int i=0;i
        
         >1]>>1)|((i&1)<<(l-1));    for(int i=0;i
         
          
           >1,N; CDQ(l,mid); for(N=1;N<=mid-l+1+r-l;N<<=1); for(int i=l;i<=mid;++i)L[i-l]=g[i]; for(int i=0;i<=r-l;++i)R[i]=A[i]*jv[i]; NTT(L,1,N);NTT(R,1,N); for(int i=0;i