最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Codeforces 1278 F Cards 增强版 题解 (斯特林数，推式子)

来源：博客园

原题链接

增强版链接


(相关资料图)

增强版中k=1e7

为啥网上题解的式子都那么长啊.jpg

首先令\(p=\frac 1m\)。求某个数的次幂的题通常都是无脑转下降幂：\(x^k=\sum_{i=0}^k S_2(k,i)x^{\underline i}\)，其中\(S_2\)表示第二类斯特林数，\(x^{\underline i}\)表示下降幂，也就是\(\binom xi i!\)(i>x时值为0)。对于一种实际赢了\(x\)场的情况，\(S_2(k,j)\)对它的答案贡献应为\(\binom xjj!\)。因此我们可以把这个组合数中的每一种选取情况拿出来分别计算贡献，所以最终答案\(=\sum_{j=0}^k S_2(k,j)\binom njj!p^j\)，这一步转化也可以列式子推，但是能用组合意义还是用吧。第二类斯特林数是可以\(O(klogk)\)求出一行的，如果NTT板子牛逼的话是可以过这题的，但有\(O(k)\)的做法。

有一个关于第二类斯特林数的公式：\(S_2(k,j)=\frac 1{j!}\sum_{i=0}^j (-1)^{j-i}\binom ji i^k\)。直接带入上面的式子得到：\(ans=\sum_{j=0}^k\sum_{i=0}^j (-1)^{j-i} \frac{n!}{i!(j-i)!(n-j)!}p^ji^k\)。这相当于是我们要把n个元素组成的集合分割成3份，大小分别为\(i,j-i,n-j\)(都可以为0，且前两部分大小之和\(\le k\))，其中第一部分的"权值"为\(i^kp^i\)，第二部分的权值为\((-p)^{j-i}\)，第三部分的权值为1，求所有分割方式的权值之积的和。我们枚举i，尝试把剩下的权值\(O(1)\)求出。改写一下答案：\(ans=\sum_{i=0}^k i^kp^i f(i)\)，其中\(f(i)=\sum_{j=0}^{k-i}\binom{n-i}j(-p)^j\ \ (注意这里的j不是上面的j了)\)，我们想要\(O(k)\)求出\(f_0\cdots f_k\)。

其实f是可以差分之后递推求的。注意到\(f_k=1\)，所以我们反向差分：

\[\begin{align}f_i-f_{i+1}&=(\sum_{j=0}^{k-i}\binom{n-i}j(-p)^j)-(\sum_{j=0}^{k-i-1}\binom{n-i-1}j(-p)^j)\\&=\binom{n-i}{k-i}(-p)^{k-i}+\sum_{j=0}^{k-i-1}[\binom{n-i}j-\binom{n-i-1}j](-p)^j\\&=\binom{n-i}{k-i}(-p)^{k-i}+\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^j\ \ 考虑组合数的递推公式\\\end{align}\]

再看看这个式子的后半部分等于什么：

\[\begin{align}&\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^j\\=&(-p)\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^{j-1}\\=&(-p)\sum_{j=0}^{k-i-2}\binom{n-i-1}j(-p)^j\\=&(-p)(f_{i+1}-\binom{n-i-1}{k-i-1}(-p)^{k-i-1})\end{align}\]

因此只要预处理一下组合数就能\(O(k)\)求f了，也就是预处理\(g_i=\binom{n-i}{k-i}\)，这个很容易\(O(k)\)求。

在\(ans=\sum_{i=0}^k i^kp^i f(i)\)中，求出了f还需要\(O(k)\)对所有i求\(i^kp^i\)，这个东西是积性的，所以可以线性筛。但是快速幂常数不大所以应该也是可以过的。

时间复杂度\(O(k)\)。下面代码里用了快速幂，是\(O(klogk)\)，没有特意去卡洛谷上的时间和空间。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL n,m,k,f[10000010],p,fac[10000010],inv[10000010],cval[10000010],mpp[10000010];int main(){  fileio();  freopen("sanhok.in","r",stdin);  freopen("sanhok.out","w",stdout);  fac[0]=1;repn(i,10000005) fac[i]=fac[i-1]*i%MOD;  inv[10000003]=qpow(fac[10000003],MOD-2);  for(int i=10000002;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;  cin>>n>>m>>k;  p=qpow(m,MOD-2);  LL bas=(MOD-p)%MOD;  mpp[0]=1;repn(i,10000005) mpp[i]=mpp[i-1]*bas%MOD;    cval[k]=1;//cval[i]=C(n-i,k-i)  LL cmul=1;  for(int i=k-1;i>=0;--i)  {    (cmul*=(n-i))%=MOD;    cval[i]=cmul*inv[k-i]%MOD;  }  f[k]=1;  for(int i=k-1;i>=0;--i)  {    f[i]=(f[i+1]+cval[i]*mpp[k-i])%MOD;    LL add=(f[i+1]-mpp[k-i-1]*cval[i+1]%MOD+MOD)%MOD;    (add*=(MOD-p))%=MOD;    (f[i]+=add)%=MOD;  }  LL pi=1,mul=1,ans=0;  rep(i,k+1)  {    LL val=pi*qpow(i,k)%MOD*mul%MOD*inv[i]%MOD;    (pi*=p)%=MOD;(mul*=(n-i))%=MOD;    (ans+=val*f[i])%=MOD;  }  cout<

关键词： 第二部分 递推公式 点击查看