C题
设计状态:
表示在第i次出牌,表示没出。
当第i位是2时:
是,表示前面为的个数,是,表示除了前面为的剩下的所有。
就是到第轮,没有把第i位换掉的概率,而前面的2是一定要被换掉的,否则不会到第i轮。
当第i位是3时:
统计答案的时候,次显然是的概率,因为最后一位怎么操作都是次。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e6+10; const ll mod = 998244353; ll F[maxn],Finv[maxn]; inline ll quick_pow(ll x,ll p){ ll res=1; while(p){ if(p&1)res=(res*x)%mod; x=(x*x)%mod,p>>=1; } return res; } inline ll inv(ll a){return quick_pow(a,mod - 2);} void init(){ F[0]=Finv[0]=1ll; for(int i=1;i<maxn;i++){ F[i]=F[i-1]*1ll*i%mod; Finv[i]=Finv[i-1]*1ll*inv(i)%mod; } } ll C(ll n,ll m){ if(m<0||m>n)return 0; return F[n]*1ll*Finv[n-m]%mod*Finv[m]%mod; } int sum[maxn],n; char str[maxn]; ll dp[maxn][2]; int main(){ init(); scanf("%d",&n); scanf("%s",str+1); for(int i=1;i<=n;i++){ sum[i]=sum[i-1]; if(str[i]=='2')sum[i]++; } dp[0][1]=1; for(int i=1;i<=n;i++){ ll a=i-1-sum[i-1]; ll b=n-sum[i-1]; ll p=C(b-1,a)*inv(C(b,a))%mod; if(str[i]=='2'){ dp[i][1]=dp[i-1][1]*(1-p)%mod; dp[i][0]=dp[i-1][1]*p%mod; } else dp[i][1]=dp[i-1][1]; } ll ans=0; for(int i=1;i<n;i++){ ans=(ans+1ll*i*dp[i][0])%mod; } ans=(ans+1ll*n*dp[n-1][1])%mod; ans=(ans+mod)%mod; cout<<ans<<endl; }