[HDU5819] Knights

qwq

题意

有n个格子上有n个骑士,移动速度相同,初始移动方向已知。两个骑士相遇时各有0.5概率胜。骑士走到边缘马上转向。求最右的棋子活到最后的概率。

思路

胜利当且仅当最右的骑士向左杀死所有向右运动的骑士。

$ f[i][j] $表示考虑到前i个骑士时只剩j个向右的概率。

两种情况:

当前的骑士向右时,$ f[i][j] = f[i - 1][j - 1] $。

当前骑士向左时,$ f[i][j] = \sum_{k = j}^{i - 1} f[i - 1][k] \times (\frac{1}{2})^{k - j + 1} $。

即赢k - j个再输掉。

可以转化成$ f[i][j] = \frac{f[i][j + 1] + f[i - 1][j]}{2} $。

特殊情况是$ f[i][1] $即把左边所有的都杀掉。

$ f[i][1] = f[i][2] + f[i - 1][1] $。

最终结果是$ \sum{j = 1}^{n - 1} f[n - 1][j] * (\frac{1}{2})^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
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 1010,MOD = 1000000007;
int d[N],f[N][N],inv[N];
inline void U(int &x,int y){if((x += y) >= MOD) x -= MOD;}
inline int qpow(int a,int b)
{
int r = 1;for(;b;b >>= 1)
{
if(b & 1) r = 1LL * r * a % MOD;
a = 1LL * a * a % MOD;
}
return r;
}
int main()
{
inv[0] = 1;int inv2 = (inv[1] = qpow(2,MOD - 2));
for(int i = 2;i < N;i++) inv[i] = 1LL * inv[i - 1] * inv[1] % MOD;
int T = getint();for(int t = 1;t <= T;t++)
{
int n = getint();
for(int i = 1;i <= n;i++) d[i] = getint();
f[1][1] = 1;
for(int i = 2;i <= n;i++)
{
f[i][i] = d[i] ? f[i - 1][i - 1] : 0;
if(d[i])
{
for(int j = i - 1;j;j--) f[i][j] = f[i - 1][j - 1];
}
else
{
for(int j = i - 1;j;j--)
{
if(j == 1) break;
f[i][j] = f[i][j + 1];U(f[i][j],f[i - 1][j]);
f[i][j] = 1LL * f[i][j] * inv2 % MOD;
}
f[i][1] = f[i][2];U(f[i][1],f[i - 1][1]);
}
}
int ans = 0;
for(int j = 1;j < n;j++) U(ans,1LL * inv[j] * f[n - 1][j] % MOD);
printf("Case #%d: %d\n",t,ans);
}
return 0;
}