题解 P6031 【CF1278F Cards 加强版】
command_block
·
·
题解
一道 组合数&斯特林数 处理的练习题。
可以观察出,每次洗牌是独立的。
设第一张是王牌的概率为p=\frac{1}{m},不是的概率即为1-p
那么就是要求计算如下式子
\sum\limits_{i=0}^n\dbinom{n}{i}p^i(1-p)^{n-i}i^k
意义 : 枚举洗出王牌的次数,选出若干轮,乘上对应概率和贡献。
然后观察到n大,k小,容易想到使用第二类斯特林数展开幂次。
有m^n=n个球放进m个有区别的箱子里,允许空盒的方案数。
第二类斯特林数\begin{Bmatrix}n\\m\end{Bmatrix}为将n个球放入m个无区别的盒子中,无空盒的方案数。
m^n=\sum\limits_{i=0}^{\min(n,m)}\dbinom{m}{i}i!\begin{Bmatrix}n\\i\end{Bmatrix}
等号右边的组合意义是 : 选出盒子,盒子排列,向盒子里放球。
代入最开始的式子可得 :
\sum\limits_{i=0}^n\dbinom{n}{i}p^i(1-p)^{n-i}\sum\limits_{j=0}^k\dbinom{i}{j}j!\begin{Bmatrix}k\\j\end{Bmatrix}
\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=0}^n\dbinom{i}{j}\dbinom{n}{i}p^i(1-p)^{n-i}
考虑后面的\sum\limits_{i=0}^n\dbinom{i}{j}\dbinom{n}{i}p^i(1-p)^{n-i}
广义的情形 : \sum\limits_{i=0}^n\dbinom{i}{j}\dbinom{n}{i}a^ib^{n-i}
=\sum\limits_{i=0}^n\dfrac{i!n!}{j!(i-j)!i!(n-i)!}a^ib^{n-i}
=\dfrac{1}{j!}\sum\limits_{i=0}^n\dfrac{n!}{(i-j)!(n-i)!}a^ib^{n-i}
=\dfrac{n!}{j!(n-j)!}\sum\limits_{i=0}^n\dfrac{(n-j)!}{(i-j)!(n-i)!}a^ib^{n-i}
=a^j\dbinom{n}{j}\sum\limits_{i=0}^n\dbinom{n-j}{i-j}a^ib^{n-i}
=a^j\dbinom{n}{j}\sum\limits_{i=0}^{n-j}\dbinom{n-j}{i}a^ib^{n-i-j}
=a^j\dbinom{n}{j}(a+b)^{n-j}
注意对于n\leq k不合法,此时直接按照最初的暴力式计算即可。
后面的部分就是\dbinom{n}{j}p^j,代回原式可得
=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}p^j
求出一行第二类斯特林数就可以计算了,
原题可以直接O(k^2)递推。
使用NTT,复杂度为O(klogk)。
我们还不满足于这个复杂度,考虑对
m^n=\sum\limits_{i=0}^{m}\dbinom{m}{i}i!\begin{Bmatrix}n\\i\end{Bmatrix}
二项式反演得到:
\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{i=0}^{m}(-1)^{m-i}\dbinom{m}{i}i^n
回代到最后的式子
=\sum\limits_{j=0}^k\frac{1}{j!}\sum\limits_{i=0}^{j}(-1)^{j-i}\dbinom{j}{i}i^kj!\dbinom{n}{j}p^j
=\sum\limits_{i=0}^{k}(-1)^ii^k\sum\limits_{j=i}^k\dbinom{n}{j}\dbinom{j}{i}(-p)^j
=\sum\limits_{i=0}^{k}(-1)^ii^k\sum\limits_{j=i}^k\dfrac{n!j!}{j!(n-j)!i!(j-i)!}(-p)^j
=\sum\limits_{i=0}^{k}(-1)^ii^k\dbinom{n}{i}\sum\limits_{j=i}^k\dbinom{n-i}{j-i}(-p)^j
=\sum\limits_{i=0}^{k}i^k\dbinom{n}{i}p^i\sum\limits_{j=0}^{k-i}\dbinom{n-i}{j}(-p)^j
观察后面的S(i)=\sum\limits_{j=0}^{k-i}\dbinom{n-i}{j}(-p)^{j},似乎并没有一个很好的封闭形式。
我们考虑裂开组合数递推(手残裂错了一次qwq):
=\sum\limits_{j=0}^{k-i}\Bigg(\dbinom{n-i-1}{j}+\dbinom{n-i-1}{j-1}\Bigg)(-p)^{j}
=S(i+1)+\dbinom{n-i-1}{k-i}(-p)^{k-i}+\sum\limits_{j=0}^{k-i}\dbinom{n-i-1}{j-1}(-p)^{j}
令C=S(i+1)+\dbinom{n-i-1}{k-i}(-p)^{k-i}。
=C+(-p)\sum\limits_{j=0}^{k-i}\dbinom{n-i-1}{j-1}(-p)^{j-1}
=C+(-p)\sum\limits_{j=0}^{k-i-1}\dbinom{n-i-1}{j}(-p)^{j}
得到S(i)=C+(-p)S(i+1)
即S(i)=(1-p)S(i+1)+\dbinom{n-i-1}{k-i}(-p)^{k-i},边界是S(k)=1
回到原式=\sum\limits_{i=0}^{k}i^k\dbinom{n}{i}p^iS(i)
线性筛一下id_k就可以O(k)完成了。
对于$\dbinom{n-i-1}{k-i}$就更烦了。
有吸收公式$\dfrac{n-i-1}{k-i}\dbinom{n-i-1}{k-i}=\dfrac{}{}\dbinom{n-(i+1)-1}{k-(i+1)}
这还需要额外的求逆元,似乎也可以线性筛。
代码里使用了较多卡常技巧。
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 998244353
#define MaxK 10050000
using namespace std;
ll powM(ll a,int t=mod-2)
{
ll ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int n,m,k,c;
int p[MaxK],id[MaxK],inv[MaxK],tn;
void getsth(int lim)
{
inv[1]=id[1]=1;
for (int i=2;i<=lim;i++){
if (!id[i]){
id[i]=powM(p[++tn]=i,k);
inv[i]=powM(i);
}for (int j=2,t;j<=tn&&(t=i*p[j])<=lim;j++){
id[t]=1ll*id[i]*id[p[j]]%mod;
inv[t]=1ll*inv[i]*inv[p[j]]%mod;
if (i%p[j]==0)break;
}
}
}
void solve1()
{
getsth(k);
int p=powM(m),q=mod+1-p;
ll x1=1,x2=powM(q,n),C=1,ans=0;
q=powM(q);
for (int i=1;i<=k;i++){
x1=x1*p%mod;
x2=x2*q%mod;
C=C*(n-i+1)%mod*inv[i]%mod;
ans=(ans+x1*x2%mod*C%mod*id[i])%mod;
}printf("%lld",ans);
}
int S[MaxK];
void solve2()
{
getsth(k);
int p=powM(m);
ll C=1,x=1;S[k]=1;
for (int i=k-1;i;i--){
C=C*(n-i-1)%mod*inv[k-i]%mod;
x=x*(mod-p)%mod;
S[i]=(1ll*S[i+1]*(mod+1-p)+C*x)%mod;
}
C=x=1;ll ans=0;
for (int i=1;i<=k;i++){
x=x*p%mod;
C=C*(n-i+1)%mod*inv[i]%mod;
ans=(ans+S[i]*C%mod*id[i]%mod*x)%mod;
}printf("%lld",ans);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
if (m==1){printf("%lld",powM(n,k));return 0;}
if (n<=k)solve1();
else solve2();
return 0;
}