Codeforces 1156F Card Bag
题目链接
https://codeforces.com/contest/1156/problem/F
题目大意
有 $n$ 个卡片，每个卡片上的数字为 $a_i$ 。每次等概率从这对卡里面抽出一个卡，假设 $x$ 为本次抽出来的卡片， $y$ 为上一次抽出的卡片，那么如果 $x < y$ 那么你就输了；如果 $x = y$ 你就获胜；如果 $x > y$ 那么比赛会继续。问你获胜的概率为多少。
题目分析
定义 $f[i][j]$ 为取大小为 $i$ 的数 $1$ 次，且这是取出来的第 $j$ 个数的概率为多少。那么显然有：
$$f[i][j] = \sum\limits_{k=1}^{i-1}{f[k][j – 1] \cdot \frac{cnt[i]}{n – j + 1}}$$
其中 $cnt[i]$ 为 $i$ 的出现次数。
注意到其中的求和可以使用前缀和来优化。
统计答案时只需要统计其中 $cnt[i] > 1$ 且连续取出来两次的情况即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 5005;
long long mod = 998244353;
int n, m, t;
long long inv[maxn];
long long cnt[maxn];
long long f[maxn][maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
x >>= 1;
b = b * b % mod;
}
return ret;
}
int main(){
int i, j;
int x, y;
long long ans = 0;
for(i=1;i<=5000;i++){
inv[i] = qpow(i, mod - 2);
}
n = read();
for(i=1;i<=n;i++){
x = read();
cnt[x]++;
}
for(i=1;i<=n;i++){
f[i][1] = cnt[i] * inv[n] % mod;
if(cnt[i] > 1)ans += cnt[i] * (cnt[i] - 1) % mod * inv[n] % mod * inv[n - 1] % mod;
ans %= mod;
f[i][1] += f[i - 1][1];
for(j=2;j<=n;j++){
f[i][j] = f[i - 1][j - 1] * cnt[i] % mod * inv[n - j + 1] % mod;
if(cnt[i] > 1)ans += f[i - 1][j - 1] * cnt[i] % mod * (cnt[i] - 1) % mod * inv[n - j + 1] % mod * inv[n - j] % mod;
ans %= mod;
f[i][j] += f[i - 1][j];
}
}
printf("%lld\n", ans);
return 0;
}