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^2C\log 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_i\leq 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!\cdot\sum_{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<bits/stdc++.h>
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]<i) swap(a[rev[i]],a[i]);
for(int l=2; l<=n; l<<=1) {
for(ll *p=a; p!=a+n; p+=l) {
for(int i=0,m=l>>1; i<m; ++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<LenA+LenB; n<<=1);
FOR(i,0,n-1) a[i]=b[i]=0;
FOR(i,0,LenA-1) a[i]=A[i];
FOR(i,0,LenB-1) b[i]=B[i];
DFT(a,n,1);DFT(b,n,1);
FOR(i,0,n-1) C[i]=a[i]*b[i]%Mod;
DFT(C,n,-1);
}
ll Fac[M],Inv[M];
ll a[12][N];
ll b[N],g[N];
ll C(int n,int m) {
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("%lld\n",res);
}
return 0;
}
|