首页 > 其他分享 >Codeforces Global Round 10 H. ZS Shuffles Cards

Codeforces Global Round 10 H. ZS Shuffles Cards

时间:2022-12-01 15:36:42浏览次数:69  
标签:10 int Global 一轮 Codeforces 步数 考虑 转移 DP

题目链接

设f[i]表示还有i个数不在集合内的期望步数,尝试列一下转移式,会发现式子由转移到下一轮的期望步数之后的DP值组成,考虑DP的转移过程,就会发现答案为转移到下一轮的期望步数$\times $期望的轮数(即把前者设为1之后的DP值)。

前者是易求的,考虑后者,如果直接考虑一轮第一次遇到0时,前面有几个有效数,是很难以优化的(转移到的状态不同)。

换一个角度,仅考虑这轮的第一张牌是什么:但如果分三种情况考虑,肯定转移不到相同的状态;但发现已经出现过的牌是没有意义的,所以直接略过,那么只考虑没出现的牌和0。如果是0,那么直接跳到下一轮,转移到\(f[i]+1\);如果是没出现过的牌,那么在【不考虑已经出现过的牌】的情况下,相当于转移到\(f[i-1]\)!(因为在考虑下一张牌的时候,两者的概率都是符合的!)值得注意的是,初始值\(f[0]=1\),因为这相当于刚取完最后一种牌,还需要遇到一个0来增加一轮。

其实从取牌的过程来看,就相当于考虑下一张牌是0或者没出现过的牌的概率。遇到0的时候轮数+1,否则状态+1,而目前的状态又恰好能退出下一张牌的概率!

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5,P=998244353;
int fpw(int a,int x){
	int s=1;
	for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
	return s;
}
void A(int& x,int y){
	x+=y;
	if(x>=P) x-=P;
}
int n,m,iv[N],s1,s2,t;
int main()
{
	cin>>n>>m;
	s1=t=1;
	for(int i=1;i<=n+m;i++) iv[i]=fpw(i,P-2);
	for(int i=1;i<=n;i++){
		t=1ll*t*iv[n+m-i+1]%P*(n-i+1)%P;	
		A(s1,t);
	}
	for(int i=1;i<=n;i++) A(s2,iv[i]);
	s2=(1ll*s2*m+1)%P;
	cout<<1ll*s1*s2%P<<endl;
	return 0;
}

标签:10,int,Global,一轮,Codeforces,步数,考虑,转移,DP
From: https://www.cnblogs.com/szsz/p/16941512.html

相关文章