2022牛客多校#4 C. Easy Counting Problem

定义好字符串，满足：

• 包含十进制下小于 w ( 2 ≤ w ≤ 10 ) w(2 leq w leq 10) w(2≤w≤10) 的数字
• 数字 i i i 至少出现 c i ( 1 ≤ c i ≤ 50000 , ∑ c i ≤ 50000 ) c_i(1 leq c_i leq 50000,sum c_i leq 50000) ci​(1≤ci​≤50000,∑ci​≤50000) 次

有 q ( 1 ≤ q ≤ 300 ) q(1 leq q leq 300) q(1≤q≤300) 次询问，每次询问求解有多少个不同的长度为 n ( 1 ≤ n ≤ 1 0 7 ) n(1 leq n leq 10^7) n(1≤n≤107) 的好字符串。

考虑生成函数，由于求排列计数，因此考虑EGF。
数字 k k k 至少出现 c k c_k ck​ 次，其对应的EGF为
f k ( x ) = x c k c k ! + x c k + 1 ( c k + 1 ) ! + x c k + 2 ( c k + 2 ) ! + . . . = e x − ∑ i = 0 c k − 1 x i i ! begin{aligned} f_k(x)&=frac{x^{c_k}}{c_k!}+frac{x^{c_k+1}}{(c_k+1)!}+frac{x^{c_k+2}}{(c_k+2)!}+...\ &=e^x-sum_{i=0}^{c_k-1}{frac{x^i}{i!}} end{aligned} fk​(x)​=ck​!xck​​+(ck​+1)!xck​+1​+(ck​+2)!xck​+2​+...=ex−i=0∑ck​−1​i!xi​​

所有条件汇总的EGF为
F ( x ) = ∏ k = 0 w − 1 f k ( x ) = ∏ k = 0 w − 1 ( e x − ∑ i = 0 c k − 1 x i i ! ) F(x)=prod_{k=0}^{w-1}{f_k(x)}=prod_{k=0}^{w-1}(e^x-sum_{i=0}^{c_k-1}{frac{x^i}{i!}}) F(x)=k=0∏w−1​fk​(x)=k=0∏w−1​(ex−i=0∑ck​−1​i!xi​)

对于每个询问的 n n n ， F ( x ) F(x) F(x) 的 [ x n n ! ] [frac{x^n}{n!}] [n!xn​] 的系数即为答案。
a n s n = [ x n n ! ] ∏ k = 0 w − 1 ( e x − ∑ i = 0 c k − 1 x i i ! ) ans_n=[frac{x^n}{n!}]prod_{k=0}^{w-1}(e^x-sum_{i=0}^{c_k-1}{frac{x^i}{i!}}) ansn​=[n!xn​]k=0∏w−1​(ex−i=0∑ck​−1​i!xi​)

上式无法直接卷积，考虑单独提出 e x e^x ex
F ( x ) = ∑ i = 0 w − 1 e i x ⋅ ( − 1 ) w − 1 − i ⋅ g w − 1 , w − 1 − i ( x ) F(x)=sum_{i=0}^{w-1}e^{ix}cdot (-1)^{w-1-i} cdot g_{w-1,w-1-i}(x) F(x)=i=0∑w−1​eix⋅(−1)w−1−i⋅gw−1,w−1−i​(x)

其中 g i , j g_{i,j} gi,j​ 表示在 { ∑ k = 0 c i − 1 x k k ! } {sum_{k=0}^{c_i-1}{frac{x^k}{k!}}} {∑k=0ci​−1​k!xk​} 的前 i i i 项中，选取了 j j j 项之积的表达式之和。存在转移式
g i , j = g i − 1 , j + g i − 1 , j − 1 ⋅ ∑ k = 0 c i − 1 x k k ! g_{i,j}=g_{i-1,j}+g_{i-1,j-1}cdot sum_{k=0}^{c_i-1}{frac{x^k}{k!}} gi,j​=gi−1,j​+gi−1,j−1​⋅k=0∑ci​−1​k!xk​

可以采用NTT在 O ( w 2 C log ⁡ C ) O(w^2Clog C) O(w2ClogC) 的复杂度内（其中 C = ∑ c i C=sum c_i C=∑ci​），求解出所有的 g i , j ( x ) g_{i,j}(x) gi,j​(x) ，并且其最高次不超过 C C C 。

考虑拆开 e i x = ∑ j = 0 + ∞ i j j ! x j e^{ix}=sum_{j=0}^{+infty}{frac{i^j}{j!}x^j} eix=∑j=0+∞​j!ij​xj ，
F ( x ) = ∑ i = 0 w − 1 ( − 1 ) w − 1 − i ⋅ g w − 1 , w − 1 − i ( x ) ∑ j = 0 + ∞ i j j ! x j = ∑ i = 0 w − 1 h i ( x ) ∑ j = 0 + ∞ i j j ! x j begin{aligned} F(x)&=sum_{i=0}^{w-1}(-1)^{w-1-i} cdot g_{w-1,w-1-i}(x)sum_{j=0}^{+infty}{frac{i^j}{j!}x^j}\ &=sum_{i=0}^{w-1}h_i(x)sum_{j=0}^{+infty}{frac{i^j}{j!}x^j} end{aligned} F(x)​=i=0∑w−1​(−1)w−1−i⋅gw−1,w−1−i​(x)j=0∑+∞​j!ij​xj=i=0∑w−1​hi​(x)j=0∑+∞​j!ij​xj​

求解上式中 [ x n n ! ] [frac{x^n}{n!}] [n!xn​] 的系数，由于最高次 C = ∑ c i ≤ 50000 C=sum c_ileq 50000 C=∑ci​≤50000 ，依次可以枚举 h i ( x ) h_i(x) hi​(x) 中第 k k k 项 x k x^k xk 的系数 [ x k ] h i ( x ) [x^k]h_i(x) [xk]hi​(x) ，则还需在 ∑ j = 0 + ∞ i j j ! x j sum_{j=0}^{+infty}{frac{i^j}{j!}x^j} ∑j=0+∞​j!ij​xj 中选取 n − k n-k n−k 项的系数，即 i n − j ( n − j ) ! frac{i^{n-j}}{(n-j)!} (n−j)!in−j​

因此答案为
a n s n = n ! ⋅ ∑ i = 0 w − 1 ∑ k = 0 n i n − j ( n − j ) ! [ x k ] h i ( x ) ans_n=n!cdotsum_{i=0}^{w-1}sum_{k=0}^n{frac{i^{n-j}}{(n-j)!}[x^k]h_i(x)} ansn​=n!⋅i=0∑w−1​k=0∑n​(n−j)!in−j​[xk]hi​(x)

其中 n ! n! n! 用于将 x n x^n xn 的系数转化为 [ x n n ! ] [frac{x^n}{n!}] [n!xn​] 的系数。

来自SolitaryDrea

#include
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int Mod=998244353;
const int N=2e5+50;
const int M=1e7+50;
bool __;

ll Fast(ll x,int b) {
	ll t=1;
	for(; b; b>>=1,x=x*x%Mod) {
		if(b&1) t=t*x%Mod;
	}
	return t;
}
void DFT(ll *a,int n,int f) {
	static int rev[N],ww[N],iw[N],pn=0;
	if(pn!=n) {
		ll p=Fast(3,(Mod-1)/n);
		ww[0]=1;
		FOR(i,1,n-1) ww[i]=ww[i-1]*p%Mod;
		iw[n-1]=Fast(ww[n-1],Mod-2);
		DOR(i,n-1,1) iw[i-1]=iw[i]*p%Mod;
		FOR(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
		pn=n;
	}
	int *w=(f>0)?ww:iw;
	FOR(i,0,n-1) if(rev[i]
		for(ll *p=a; p!=a+n; p+=l) {
			for(int i=0,m=l>>1; i
				ll t=p[i+m];
				p[i+m]=(p[i]+w[n/l*(i+m)]*t)%Mod;
				p[i]=(p[i]+w[n/l*i]*t)%Mod;
			}
		}
	}
	if(f<0) {
		ll t=Fast(n,Mod-2);
		FOR(i,0,n-1) a[i]=a[i]*t%Mod;
	}
}
void Poly_Mul(const ll *A,int LenA,const ll *B,int LenB,ll *C) {
	static ll a[N],b[N];
	int n=1;for(; n
	return Fac[n]*Inv[n-m]%Mod*Inv[m]%Mod;
}
bool ___;
int main() {
	int n=1e7;
	Fac[0]=1;
	FOR(i,1,n) Fac[i]=Fac[i-1]*i%Mod;
	Inv[n]=Fast(Fac[n],Mod-2);
	DOR(i,n,1) Inv[i-1]=Inv[i]*i%Mod;
	int w;
	scanf("%d",&w);
	a[0][0]=1;
	int K=0;
	FOR(i,1,w) {
		int c;
		scanf("%d",&c);
		FOR(i,0,c-1) b[i]=-Inv[i];
		DOR(j,i-1,0) {
			Poly_Mul(a[j],K+1,b,c,g);
			FOR(k,0,K+c-1) a[j+1][k]=(a[j+1][k]+g[k])%Mod;
		}
		
		K+=c-1;
	}
	int q;
	scanf("%d",&q);
	while(q--) {
		scanf("%d",&n);
		ll res=0;
		FOR(i,0,w) {
			ll u=Fast(w-i,n);
			ll v=Fast(w-i,Mod-2);
			FOR(j,0,min(K,n)) {
				if(w-i) {
					res=(res+Fac[n]*a[i][j]%Mod*Inv[n-j]%Mod*u)%Mod;
					u=u*v%Mod;
				} else if(n-j==0) {
					res=(res+Fac[n]*a[i][j]%Mod*Inv[n-j]%Mod)%Mod;
				}
			}
		}
		if(res<0) res+=Mod;
		printf("%lldn",res);
	}
	return 0;
}