中国少数民族网站建设/新型网络营销方式

CF1765C Card Guessing

题目大意

桌面上有一堆牌，牌有四种花色，每种花色有$n$张，一共$4n$找张。每次随机从牌堆中抽一张直到抽完，抽出卡片的序列总共有$(4n)!$种。Monocarp在每次抽卡时会根据过去$k$次抽卡的结果来猜当前抽出卡牌的花色，他会固定猜最近$k$次结果中出现次数最小的那一个花色（如果有多种花色则任意选一个，如果之前抽卡数量小于$k$则猜测依据是之前所有的抽卡结果）。求期望猜对的次数，输出答案模$998244353$。

$1\le n\le 500$，$1\le k\le 4\times n$

题解

根据期望的线性性，期望猜对的次数等于每次猜对的概率之和。若当前是第$i$次猜测，设$t=\min (k,i-1)$，那么是否猜对只取决于第$i-t$项到第$i-1$项。我们只需要考虑一个长度为$t+1$的序列满足最后一张牌与猜测结果相同的概率。为了方便计算，我们将同种花色的牌视作互不相同的。

设$g_{i,j}$表示长度为$i$，花色最少出现的次数为$j$的序列个数。但因为同种花色的牌数量有限，所以不能用组合数来求，很难直接计算出$g$，所以我们考虑背包。

设$f_{c,i,j}$表示放了前$c$种花色，卡牌种数为$i$，最少出现次数为$j$的方案数。那么对于每个状态，我们只需枚举下一个颜色的放置个数$p$，就可以由$f_{c,i,j}$转移到$f_{c+1,i+p,\min (i,p)}$。因为同种花色的牌是互不相同的，所以转移系数为$C_{i+p}^i\times C_n^i\times i!$。

对于$j\ge 1$，$g_{i,j}=f_{4,i,j}$。而$g_{i,0}=\sum _{c=1}^3\sum _{j=1}^{i/c}{C}_4^c{f}_{c,i,j}$。设$h_i$表示长度为$i$的不同抽卡序列的个数，则$h_i=\sum _{j=0}^n{g}_{i,j}$。

在计算答案时，我们只需求出对应的$t$，然后求出满足猜测的序列的个数，再除以总方案数就能得出猜对的概率。当$i=1$时，猜对的概率为$\frac{1}{4}$。最后的答案为$\frac{1}{4}+\sum _{i=2}^{4n}\frac{\sum _{j=1}^{t/4}{g}_{t,j}\times (n-j)}{h_{t+1}}$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2000;
long long ans,jc[2005],ny[2005],h[2005],g[2005][2005],f[5][2005][2005];
long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;ny[N]=mi(jc[N],mod-2);for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
int main()
{init();long long n,k;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++) f[1][i][i]=jc[n]*ny[n-i]%mod;for(int c=1;c<4;c++){for(int i=c;i<=c*n;i++){for(int j=1;j<=i/c;j++){if(f[c][i][j]==0) continue;for(int p=1;p<=n;p++){long long tmp=C(i+p,p)*C(n,p)%mod*jc[p]%mod;f[c+1][i+p][min(j,p)]=(f[c+1][i+p][min(j,p)]+tmp*f[c][i][j]%mod)%mod;}}}}for(int i=1;i<=4*n;i++){for(int j=1;j<=n;j++){g[i][j]=f[4][i][j];}}for(int c=1;c<=3;c++){for(int i=1;i<=c*n;i++){for(int j=1;j<=i/c;j++){g[i][0]=(g[i][0]+C(4,c)*f[c][i][j]%mod)%mod;}}}for(int i=1;i<=4*n;i++){for(int j=0;j<=n;j++){h[i]=(h[i]+g[i][j])%mod;}}ans=mi(4,mod-2);for(int i=2;i<=4*n;i++){long long tmp=0;int t=min(i-1ll,k);for(int j=0;j<=t/4;j++){tmp=(tmp+g[t][j]*(n-j)%mod)%mod;}tmp=tmp*mi(h[t+1],mod-2)%mod;ans=(ans+tmp)%mod;}printf("%lld",ans);return 0;
}