我怎么这么zz啊。。。。

法一：

枚举最后一层的方案：没了。。。

法二：

生成函数：没了。

k*F^k(x)，就是错位相减。

 

法三：

我的辣鸡做法：生成函数

求方案数，用的等比数列求和。。。。多项式快速幂，，O(nlog^2n)

求贡献和，构造G，然后求导，，，，

O(nlog^2n)

慢的一批。。。。

const int N=1e5+5;int jie[N],inv[N];int n;Poly F,G;Poly ksm(Poly f,int n,int y){    Poly ret;ret.resize(1);ret[0]=1;    while(y){        if(y&1) {            ret=ret*f;ret.resize(n);        }        f=f*f;f.resize(n);        y>>=1;    }    return ret;}int main(){    int n=N-3;    jie[0]=1;    for(reg i=1;i<=n;++i) jie[i]=mul(jie[i-1],i);    inv[n]=qm(jie[n],mod-2);    for(reg i=n-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1);        Poly f;    f.resize(n);    for(reg i=1;i