题面
有 (n) 天，每天插入一个字符集大小为 (c) 长度为 (l) 的字符串，求每一天建立 ( t Trie) 树的期望节点数（根节点不算）模 (998244353)。
数据范围：(1le nle 10^5)，(1le c,lle 10^9)。
- Input
5 4 3
- Output
4
911976330
792083550
276733174
815453946
正解
转化问题：有一颗高度为 (l+1) 的 (c) 叉完全 ( t Trie)，从根到叶走 (n) 遍，求期望经过节点数（根节点不算）。
一层一层考虑，答案为（因为不考虑根节点，所以 (i) 从 (1) 开始）：(Ans(n)=sum_{i=1}^l a(i,n))。
考虑新的路径会不会走新节点，可以递推：
[a(i,n)=a(i,n-1)+frac{c^i-a(i,n-1)}{c^i}\
a(i,n)=1+a(i,n-1)(1-frac{1}{c^i})\
]
特征方程：(t=1+(1-frac{1}{c^i})tLongrightarrow t=c^i)。
[a(i,n)-c^i=(1-frac{1}{c^i})(a(i,n-1)-c^i)\
egin{split}
a(i,n)=&(1-frac{1}{c^i})(a(i,n-1)-c^i)+c^i\
=&(1-frac{1}{c^i})^n(a(i,0)-c^i)+c^i\
=&c^i-c^i(1-frac{1}{c^i})^n\
end{split}
]
带回到上面求每一天答案的式子，展开二项式 (^{color{#bcbcee}{[1]}})，交换枚举顺序 (^{color{#bceebc}{[2]}})，抵消 (^{color{#eebcbc}{[3]}})：
[egin{split}
Ans(n)=&sum_{i=1}^l a(i,n)\
=&sum_{i=1}^lleft(c^i-c^i(1-frac{1}{c^i})^n
ight)\
=&sum_{i=1}^l c^i-sum_{i=1}^lc^i(1-frac{1}{c^i})^n\
=&sum_{i=1}^l c^i-sum_{i=1}^lc^isum_{j=0}^nleft(frac{1}{c^i}
ight)^j(-1)^j{nchoose j}&^{color{#bcbcee}{[1]}}\
=&sum_{i=1}^l c^i-sum_{i=0}^n(-1)^i{nchoose i}sum_{j=1}^l c^jleft(frac{1}{c^j}
ight)^i&^{color{#bceebc}{[2]}}\
=&-sum_{i=1}^n(-1)^i{nchoose i}sum_{j=1}^l c^jleft(frac{1}{c^j}
ight)^i&^{color{#eebcbc}{[3]}}\
=&sum_{i=1}^n(-1)^{i+1}{nchoose i}sum_{j=1}^l c^jleft(frac{1}{c^j}
ight)^i\
=&sum_{i=1}^nfrac{n!}{i!(n-i)!}(-1)^{i+1}sum_{j=1}^l left(frac{1}{c}
ight)^{j(i-1)}\
=&n!sum_{i=1}^nfrac{1}{i!(n-i)!}(-1)^{i+1}sum_{j=1}^l left(frac{1}{c}
ight)^{j(i-1)}\
end{split}
]
发现有 (i!) 和 ((n-i)!)，并且每个 (Ans(x)) 都要求，所以想到 ( t NTT)。
[egin{split}
Ans(n)=&n!sum_{i=1}^nfrac{1}{i!(n-i)!}(-1)^{i+1}sum_{j=1}^l left(frac{1}{c}
ight)^{j(i-1)}\
=&n!sum_{i+j=n}left(frac{(-1)^{i+1}sum_{j=1}^l left(frac{1}{c}
ight)^{j(i-1)}}{i!}
ight)left(frac{1}{j!}
ight)\
end{split}
]
只需让 (f(n)=frac{(-1)^{n+1}sum_{j=1}^l left(frac{1}{c} ight)^{j(n-1)}}{n!})，(g(n)=frac{1}{n!}) 卷积即可。
其中 (sum_{j=1}^l left(frac{1}{c} ight)^{j(n-1)}) 可以用等比数列的公式算。
时间复杂度 (Theta(nlog))。
代码
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define be(a) a.begin()
#define en(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e5;
const int mod=998244353;
int n,l,c;
//Pow
int Pow(int a,int x){
if(!a) return 0; int res=1;
for(;x;a=(ll)a*a%mod,x>>=1)if(x&1) res=(ll)res*a%mod;
return res;
}
//NTT
int iv[N+1],f[N<<2],g[N<<2];
int up(int len){return 1<<int(ceil(log2(len)));}
void Getpoly(){
for(int i=iv[0]=1;i<=n;i++) iv[i]=(ll)iv[i-1]*i%mod;
for(int i=0;i<=n;i++) iv[i]=Pow(iv[i],mod-2);
for(int i=0;i<=n;i++) g[i]=iv[i];
for(int i=1;i<=n;i++){
int ic=Pow(Pow(c,i-1),mod-2);
int q=(ic==1)?l:(ll)ic*(Pow(ic,l)-1+mod)%mod*Pow(ic-1,mod-2)%mod;
f[i]=(ll)iv[i]*q%mod*((i&1)?1:mod-1)%mod;
}
}
const int G=3,iG=332748118;
int lim,r[N<<2];
void NTT(int a[],int t){
for(int i=0;i<lim;i++)if(i<r[i]) swap(a[i],a[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
int wn=Pow(t==1?G:iG,(mod-1)/(mid<<1));
for(int j=0;j<lim;j+=(mid<<1))
for(int w=1,k=j;k<mid+j;w=(ll)w*wn%mod,k++){
int x=a[k],y=(ll)w*a[mid+k]%mod;
a[k]=(x+y)%mod,a[mid+k]=(x-y+mod)%mod;
}
}
if(t==-1){
int ilim=Pow(lim,mod-2);
for(int i=0;i<lim;i++) a[i]=(ll)a[i]*ilim%mod;
}
}
void Mulpoly(){
lim=up(n+n);
for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)*lim>>1);
NTT(f,1),NTT(g,1);
for(int i=0;i<lim;i++) f[i]=(ll)f[i]*g[i]%mod;
NTT(f,-1);
}
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>l>>c;
Getpoly(),Mulpoly();
for(int i=1,fa=1;i<=n;i++) fa=(ll)fa*i%mod,f[i]=(ll)f[i]*fa%mod;
for(int i=1;i<=n;i++) cout<<f[i]<<'
';
return 0;
}
祝大家学习愉快！