题解 P6031 【CF1278F Cards 加强版】
command_block
2020-02-13 13:48:34
一道 组合数&斯特林数 处理的练习题。
------------
可以观察出,每次洗牌是独立的。
设第一张是王牌的概率为$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}$似乎不是很好算,考虑变成$\dfrac{n^{\underline i}}{i!}$,阶乘逆元预处理,下降幂边算边乘。
对于$\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)}$
这还需要额外的求逆元,似乎也可以线性筛。
代码里使用了较多卡常技巧。
```cpp
#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;
}
```