牛客多校第二场 E 题题解

E Falfa with Substring

E 题题意：给定长度 $nn$，问长度为 $nn$ 的纯小写字母串中出现 $kk$ 次 bit的字符串个数，需要对 $k\in [0,n]k\; \backslash in\; [0,n]$ 输出答案。$n\le 1\times 10^{6}n\backslash leq\; 1\backslash times\; 10^6$。

解法：对于恰好类问题，通常将其转化为至少或至多。

若至少出现 $kk$ 次 bit，因为这个字符串不会重叠出现，因而可以将其绑定成一个特殊字符，等效于在 $n-2kn-2k$ 个位置中选择 $kk$ 个位置填放 bit，剩余位置任选。因而至少 $kk$ 次出现的方案数为 ${\displaystyle F_k=\left(\genfrac{}{}{0px}{}{n-2k}{k}\right)26^{n-3k}}\backslash displaystyle\; F\_k=\{n-2k\backslash choose\; k\}26^\{n-3k\}$。这部分可以 $\mathcal{O}(n)\backslash mathcal\; O(n)$ 的求出。

接下来考虑容斥：恰有 $kk$ 个出现的需要从 $k^{\mathrm{\prime }},k^{\mathrm{\prime }}>kk\text{'},k\text{'}>k$ 处转移。对于某一个 $k\mathrm{’}k’$，其转移方案应当是从恰好 $k^{\mathrm{\prime }}k\text{'}$ 个 bit的方案中选择出 k个出来作为最终恰好的部分，剩余的都要扔掉。因而恰好 $kk$ 个的方案数为 ${\displaystyle G_k=F_k-\sum _{k^{\mathrm{\prime }}=k+1}^n\left(\genfrac{}{}{0px}{}{k^{\mathrm{\prime }}}{k}\right)G_{k^{\mathrm{\prime }}}}\backslash displaystyle\; G\_k=F\_k-\backslash sum\_\{k\text{'}=k+1\}^n\; \{k\text{'}\; \backslash choose\; k\}G\_\{k\text{'}\}$。

显然该式子还是没办法快速计算。注意到 ${\displaystyle F_i=\sum _{j=i}^n\left(\genfrac{}{}{0px}{}{j}{i}\right)G_j}\backslash displaystyle\; F\_i=\backslash sum\_\{j=i\}^\{n\}\; \{j\; \backslash choose\; i\}\; G\_\{j\}$，因而利用二项式反演得到 ${\displaystyle G_i=\sum _{j=i}^n(-1{)}^{j-i}\left(\genfrac{}{}{0px}{}{j}{i}\right)F_j}\backslash displaystyle\; G\_i=\backslash sum\_\{j=i\}^n\; (-1)^\{j-i\}\{j\backslash choose\; i\}F\_j$。将其进行整理：

注意到 $j-(j-i)=ij-(j-i)=i$ 为一定值，因而构成差卷积形式。使用 NTT 可以加速这一过程，总复杂度 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$。

使用队友通过的代码：

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=4e6+3,M=1e7+3,p=998244353,G=3,Gi=332748118;
int n,m,S,a[N],b[N],c[N],r[N],val[N],fac[M],inv[M],cf[N],ans;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL int ksm(int a,int b){
  int c=1;
  while(b){
  	if(b&1) c=1ll*c*a%p;
  	a=1ll*a*a%p,b>>=1;
  }
  return c;
}
IL void calc(int lim){
	for(int i=0;i<lim;++i)
	  r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
IL void init(int n){
	fac[0]=1;for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p;
	inv[n]=ksm(fac[n],p-2);
	for(int i=n;i;--i) inv[i-1]=1ll*inv[i]*i%p;
	cf[0]=1;for(int i=1;i<=n;++i) cf[i]=1ll*cf[i-1]*26%p;
}
IL void NTT(int *a,int lim,int op){
	calc(lim);
	for(int i=0;i<lim;++i)
	  if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<lim;i<<=1){
		int wn=ksm(~op?G:Gi,(p-1)/(i<<1));
		for(int j=0;j<lim;j+=i<<1){
			int w=1;
			for(int k=0;k<i;++k,w=1ll*w*wn%p){
				int x=a[j+k],y=1ll*w*a[j+i+k]%p;
				a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
			}
		}
	}
	if(op==-1){
		int inv=ksm(lim,p-2);
		for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
	}
}
IL void mul(int *a,int *b,int *c,int n,int m){
	int lim=1,_a[N],_b[N];
	while(lim<n+m-1) lim<<=1;
	memcpy(_a,a,4*n),memcpy(_b,b,4*m),
	memset(_a+n,0,4*(lim-n)),memset(_b+m,0,4*(lim-m));
	NTT(_a,lim,1),NTT(_b,lim,1);
	for(int i=0;i<lim;++i) c[i]=1ll*_a[i]*_b[i]%p;
	NTT(c,lim,-1);
}
IL int C(int n,int m){return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;}
int main()
{
	n=in(),init(n);
	int Max=n/3;
	for(int i=0;i<=Max;++i)
	  a[i]=1ll*C(n-2*i,i)*cf[n-3*i]%p*fac[i]%p;
	for(int i=0;i<=Max;++i)
	  if(i&1) b[i]=mod(p-inv[i]);
	  else b[i]=inv[i];
	reverse(a,a+Max+1);
	mul(a,b,a,Max+1,Max+1);
	reverse(a,a+Max+1);
    for(int i=0;i<=Max;++i) a[i]=1ll*a[i]*inv[i]%p;
    for(int i=0;i<=Max;++i) printf("%d ",a[i]);
    for(int i=Max+1;i<=n;++i) printf("0 ");
	return 0;
}