Description
有 $n$ 个人玩一个游戏，每一轮先随机淘汰一个人，然后剩下的每个人会被攻击一次，使其有 $p$ 的概率出局，问你一个人在被攻击 $k$ 次后投淘汰的概率是多少，对于每个 $0 \leq k < n$ 的整数 $k$ 你都要求一遍答案。注意淘汰和出局不是一个东西，虽然二者都会使玩家阵亡，但淘汰可以贡献答案，而出局不行。
Solution
吉老师的好题。
一个复杂度错误的 DP：设 $f_{i, j}$ 表示当前是第 $i$ 轮，有 $j$ 个人还活着的概率，然而这个貌似只能够做到 $O(n^3)$，过不去。
考虑换一种设状态的方法：
因为每个人都是一样的，因此我们可以让这些人按编号从小到大依次淘汰 / 出局。
设 $f_{i, j}$ 表示当前编号在 $[i + 1, n]$ 中的人都被攻击了 $j$ 次并且还活着的概率，那么有转移式：
前半种情况是打了 $i$，但是没打死，并且在 $i$ 在下一轮被淘汰了，因此 $j$ 加了 1，且系数为 $(1 - p)^{j - 1}$（前 $(j - 1)$ 次都没有打到，并且在第 $j$ 次攻击前被淘汰了）。
后半种情况是打了 $i$，并且在前 $j$ 次攻击中的某一次攻击把 $i$ 给打死了，因此 $j$ 不变，系数为 $(1 - p^j)$（$j$ 次攻击中都没打到 $i$ 的概率为 $p^j$，所有可能的情况减去一次都没打到的情况就等于至少打到一次的情况了，即 $(1 - p^j)$）。
统计答案的具体方式见代码，也可自行思考，这个部分就比较简单了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <cstdio>
#define mod 258280327LL
#define maxN 2010
long long pow_nP[maxN];
long long f[maxN][maxN];
long long pow (long long x, long long y)
{
if(!y)
{
return 1;
}
else
{
long long dq = pow(x, y >> 1);
if(!(y % 2))
{
return dq * dq % mod;
}
else
{
return dq * dq % mod * x % mod;
}
}
}
long long inv (long long x)
{
return pow(x, mod - 2);
}
int main ()
{
long long T = 0;
scanf("%lld", &T);
while(T--)
{
long long n = 0, x = 0, y = 0;
scanf("%lld %lld %lld", &n, &x, &y);
const long long nP = (y - x) * inv(y) % mod;
pow_nP[0] = 1;
for(long long i = 1;i <= n; i++)
{
pow_nP[i] = pow_nP[i - 1] * nP % mod;
}
f[0][0] = 1;
for(long long i = 1;i <= n; i++)
{
for(long long j = 0;j <= i; j++)
{
long long A = f[i - 1][j - 1] * pow_nP[j - 1] % mod;
long long B = f[i - 1][j] * (1 - pow_nP[j] + mod) % mod;
f[i][j] = (A + B) % mod;
}
}
long long Ans = 0;
for(long long j = 0;j < n; j++)
{
Ans = 0;
for(long long i = 0;i < n; i++)
{
Ans += f[i][j] * pow_nP[j] % mod;
Ans %= mod;
}
Ans *= inv(n);
Ans %= mod;
printf("%lld ", Ans);
}
printf("\n");
}
return 0;
}
|