用生成函数的思想，其实这里就是FFT

考虑根节点放的数字，从而推出F的式子

有F=C*F*F+1

（其实这里可以分治NTT，复杂度相同（理论常数更小））

二元一次方程，求根公式

+的根，因为x->0的时候，f趋近于inf，舍弃

所以是-

再化简得到：

F=2/(1+sqrt(1-4C))

 

（顺便说一下：

一般实数域下，除法分为三种，一个是实数级别的，或者求余数，或者mod意义下得到一个数（这里没有实际意义，就是为了逆元做一个定义）

复数域下，除法可能只有共轭然后变成分子的乘法

多项式的话，要不然就是带余数的多项式除法，要不然就是分数线的形式，意义就是乘这个多项式的逆（除法就是一个表示，没有实际意义）

） 

 

多项式开根即可

代码：

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=8*1e5+5;const int mod=998244353;const int G=3;const int GI=332748118;int n,m;int c[N],d[N],e[N],t[N],co[N],p[N],ni[N],l[N];int rev[N];int inv2;int qm(int x,int y){    int ret=1;    while(y){        if(y&1) ret=(ll)ret*x%mod;        x=(ll)x*x%mod;        y>>=1;    }    return ret;}int mo(int x){    return x>=mod?x-mod:x;}void NTT(int *f,int n,int c){    for(reg i=0;i
      
       rev[i]){            f[i]^=f[rev[i]]^=f[i]^=f[rev[i]];        }    }    for(reg p=2;p<=n;p<<=1){        int gen;        if(c==1) gen=qm(G,(mod-1)/p);        else gen=qm(GI,(mod-1)/p);        for(reg l=0;l
       
        >1]>>1|((i&1)?n>>1:0);    }    NTT(f,n,1);NTT(g,n,1);    for(reg i=0;i
        
         >1);    for(reg i=0;i
         
          >1]>>1|((i&1)?(2*n)>>1:0);    }    NTT(d,2*n,1);NTT(e,2*n,1);    for(reg i=0;i<2*n;++i){        g[i]=mo(mo(2*d[i])-(ll)e[i]*d[i]%mod*d[i]%mod+mod);    }    NTT(g,2*n,-1);    ll iv=qm(2*n,mod-2);    for(reg i=0;i<2*n;++i){        if(i
          
           >1); for(reg i=0;i
          
         
        
       
      
     

其实就是列出式子

然后推式子

 

不用分治NTT的话，

生成函数这里主要是：F=C*F*F+1的整体思想

也可以看做多项式优化DP系列