首页 > 其他分享 >Codeforces 1278 F Cards 增强版 题解 (斯特林数,推式子)

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

时间:2023-01-11 17:35:54浏览次数:74  
标签:1278 题解 sum 增强版 mpp binom cval inv MOD

原题链接

增强版链接

增强版中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 <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<<"\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<<ans<<endl;

  termin();
}

标签:1278,题解,sum,增强版,mpp,binom,cval,inv,MOD
From: https://www.cnblogs.com/legendstane/p/codeforces-1278-f-cards-luogu-p-6031-solution.html

相关文章

  • SOJ1711 题解
    题意给定\(n\)个在数轴的区间\([l_1,r_1],[l_2,r_2],...,[l_n,r_n]\)。定义\(I(x)\)为所有包含\([x,x+1]\)的区间形成的集合,即\(I(x)=\{k\mid[x,x+1]\subsete......
  • 搭建k8s集群初始化master节点 kubeadm init 遇到问题解决
    搭建k8s集群时遇到的问题一记,自己找了很久解决方案,也看到有些人提出类似问题后不了了之,于是发出来给网络做一次贡献kubeadminit报错”unknownserviceruntime.v1al......
  • CF850B Arpa and a list of numbers 题解 枚举
    题目链接:https://codeforces.com/problemset/problem/850/B题目大意我们定义一个数列是”坏的数列”当且仅当这个数列不为空且数列中所有元素的最大公约数为\(1\)。......
  • 题解 BZOJ3622【已经没有什么好害怕的了】
    前置知识:二项式反演problem两个\(n\leq2000\)的数组\(A,B\),元素互不相同,求有多少种将\(A,B\)配对的方法使得\(A>B\)的恰好有\(k\)对。题目改过,但是这一步转换......
  • Magic题解
    Magic题解题意简述:给定\(n\)个数\(a_1,a_2,…,a_n\),设对于数\(x\),\(|x|\)表示其在十进制下的位数,也即\(10^{|x|}\lex<10^{|x|+1}\)需要计算:\[\sum_{i=1}^n\sum_{j=i+1......
  • 选数 题解
    选数题解首先,设最初取值为\(x\),按照套路,我们设异或前缀和:\(pre_i=a_1\oplusa_2…\oplusa_i\),设\(f(x)=\left(\left\lfloor\frac{2x}{2^n}\right\rfloor+2x\right)\bmod......
  • Codeforces Round #843 (Div. 2) 题解
    A题目大意给你一个只含字母a,b字符串,要把它拆分成三段,使得其中间那段要么同时小于等于两边要么同时大于等于两边。题解由于只有a,b我们可以分讨解决如果\([2,......
  • CF1783 A-F 题解
    比赛链接:https://codeforces.com/contest/1783连续三场出4题,还行(其实感觉有两场的E都是会做的)A水题//bySkyRainWind#include<bits/stdc++.h>#definemprmake_pai......
  • 「JOI Open 2022」Giraffes 题解
    设我们将要给出的观感好的排列为\(q\),我们希望求出\(\sum[p_i=q_i]\)的最大值(这里指不移动的长颈鹿个数)。结论一:当且仅当左右端点有当前区间最大值或者最小值时条件才......
  • 题解1
    离散化1.为什么要离散化当数据很大的时候,以至于我们不能直接使用它的时候,就要考虑将其用另外一种形式表达,通常是将其映射为数组下标。2.离散化本质本质:映射3.离......