我怎么这么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<n;++i){f[i]=inv[i];}Poly t=ksm(f,n,n),d=(-f)+1;Poly q=(-t)+1;F=f*q;F.resize(n);F=F*(~d);F.resize(n);// for(reg i=0;i<n;++i){// cout<<mul(F[i],jie[i])<<" ";// }cout<<endl; G=F*f;G.resize(n+1);G=Diff(G);f=Diff(f);G=G*(~f);G.resize(n);G=G-F;// for(reg i=0;i<n;++i){// cout<<mul(G[i],jie[i])<<" ";// }cout<<endl;// return 0;int T;rd(T);while(T--){rd(n);int ans=mul(G[n],qm(F[n]));printf("%d\n",ans);}return 0; }} signed main(){Miracle::main();return 0; }