提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

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

2023-04-18 15:19:56 时间

原题链接

增强版链接

增强版中k=1e7

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

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

有一个关于第二类斯特林数的公式：(S_2(k,j)=frac 1{j!}sum_{i=0}^j (-1)^{j-i}inom ji i^k)。直接带入上面的式子得到：(ans=sum_{j=0}^ksum_{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}inom{n-i}j(-p)^j (注意这里的j不是上面的j了))，我们想要(O(k))求出(f_0cdots f_k)。

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

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

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

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

因此只要预处理一下组合数就能(O(k))求f了，也就是预处理(g_i=inom{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 <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"

EXECUTION 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<<ans<<endl;

  termin();
}

相关文章