I Chiitoitsu
Villages: Landlines
https://ac.nowcoder.com/acm/contest/33186/A
题期望dp
设表示牌堆里剩张牌,还差个对子还需摸多少次
注意还差个对子手里还有个单牌,摸到不同于手里的牌,不管是否替换掉手里的牌,牌堆里仍有个是需要的牌
在当前状态考虑摸一次牌,有两种情况
- 有的概率摸到需要的牌,此后牌堆少一张牌,所需对子少1,即还需摸次
- 有的概率摸到不是所需要的牌,此后牌堆少一张牌,所需对子不变,即还需摸次
注意无论是哪种情况,都摸了一次牌
所以有
注意取模,初值
初始时牌堆有张牌,答案就是在处理完所需对子后
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 202;
const int mod = 1000000007;
int T, n;
char s[maxn];
int inv[maxn];
int f[maxn][maxn], num[4][maxn];
void deal (int n)
{
inv[1] = 1;
for (int i = 2; i <= n; ++i) inv[i] = (-1ll * mod / i * inv[mod % i] % mod + mod) % mod;
}
void solve (int n)
{
for (int i = 3; i <= n; ++i)
for (int j = 1; j <= 7 && 3 * (2 * j - 1) <= i; ++j) {
f[i][j] = 3ll * (2 * j - 1) * inv[i] % mod * (f[i - 1][j - 1] + 1) % mod;
f[i][j] = (f[i][j] + 1ll * (i - 3 * (2 * j - 1)) * inv[i] % mod * (f[i - 1][j] + 1) % mod) % mod;
}
}
int main ()
{
deal(136);
solve(136);
cin >> T;
for (int k = 1; k <= T; ++k) {
cin >> s + 1;
int t = 0;
for (int i = 1; i <= 26; i += 2) {
int x = s[i] - '0', cur;
if (s[i + 1] == 'm') cur = 0;
else if (s[i + 1] == 'p') cur = 1;
else if (s[i + 1] == 'z') cur = 2;
else cur = 3;
++num[cur][x];
if (num[cur][x] == 2) ++t;
}
memset(num, 0, sizeof(num));
cout << "Case #" << k << ": ";
cout << f[123][7 - t] << endl;
}
return 0;
}