题解 P6031 【CF1278F Cards 加强版】

command_block

2020-02-13 13:48:34

Solution

一道 组合数&斯特林数 处理的练习题。 ------------ 可以观察出,每次洗牌是独立的。 设第一张是王牌的概率为$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; } ```