题解-Words

题面

Words

有 \(n\) 天，每天插入一个字符集大小为 \(c\) 长度为 \(l\) 的字符串，求每一天建立 \(\tt Trie\) 树的期望节点数（根节点不算）模 \(998244353\)。

数据范围：\(1\le n\le 10^5\)，\(1\le c,l\le 10^9\)。

Input

5 4 3

Output

正解

转化问题：有一颗高度为 \(l+1\) 的 \(c\) 叉完全 \(\tt 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})t\Longrightarrow t=c^i\)。

\[a(i,n)-c^i=(1-\frac{1}{c^i})(a(i,n-1)-c^i)\\
\begin{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]}}\)：

\[\begin{split}
Ans(n)=&\sum_{i=1}^l a(i,n)\\
=&\sum_{i=1}^l\left(c^i-c^i(1-\frac{1}{c^i})^n\right)\\
=&\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^i\sum_{j=0}^n\left(\frac{1}{c^i}\right)^j(-1)^j{n\choose j}&^{\color{#bcbcee}{[1]}}\\
=&\sum_{i=1}^l c^i-\sum_{i=0}^n(-1)^i{n\choose i}\sum_{j=1}^l c^j\left(\frac{1}{c^j}\right)^i&^{\color{#bceebc}{[2]}}\\
=&-\sum_{i=1}^n(-1)^i{n\choose i}\sum_{j=1}^l c^j\left(\frac{1}{c^j}\right)^i&^{\color{#eebcbc}{[3]}}\\
=&\sum_{i=1}^n(-1)^{i+1}{n\choose i}\sum_{j=1}^l c^j\left(\frac{1}{c^j}\right)^i\\
=&\sum_{i=1}^n\frac{n!}{i!(n-i)!}(-1)^{i+1}\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(i-1)}\\
=&n!\sum_{i=1}^n\frac{1}{i!(n-i)!}(-1)^{i+1}\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(i-1)}\\
\end{split}
\]

发现有 \(i!\) 和 \((n-i)!\)，并且每个 \(Ans(x)\) 都要求，所以想到 \(\tt NTT\)。

\[\begin{split}
Ans(n)=&n!\sum_{i=1}^n\frac{1}{i!(n-i)!}(-1)^{i+1}\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(i-1)}\\
=&n!\sum_{i+j=n}\left(\frac{(-1)^{i+1}\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(i-1)}}{i!}\right)\left(\frac{1}{j!}\right)\\
\end{split}
\]

只需让 \(f(n)=\frac{(-1)^{n+1}\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(n-1)}}{n!}\)，\(g(n)=\frac{1}{n!}\) 卷积即可。

其中 \(\sum_{j=1}^l \left(\frac{1}{c}\right)^{j(n-1)}\) 可以用等比数列的公式算。

时间复杂度 \(\Theta(n\log)\)。

代码

#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]<<'\n';

	return 0;

}

祝大家学习愉快！

巴特西

题解-Words

题面

正解

代码

最新文章

热门文章