自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:16:42，当前版本为作者最后更新于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)}$

这还需要额外的求逆元,似乎也可以线性筛。

代码里使用了较多卡常技巧。

#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;
}