LuoGu: CF908D New Year and Arbitrary Arrangement
CF: D. New Year and Arbitrary Arrangement
首先要明白题意，一个序列 ab 指 $i$ 位置存在一个 a 并且 $j$ 位置存在一个 b ，满足 i < j 的不同二元组 $(i, j)$ 记为一个答案。可以发现，当前序列如果有 $k$ 个 a ，那么增加一个 b 将会使答案增加 $k$ 。
考虑 DP ，$f _ {i, j}$ 表示当前有 $i$ 个 a ，已经有 $j$ 个答案，满足终止条件后的期望答案。那么有：
$$
f _ {i, j} = \frac {p _ a} {p _ a + p _ b} f _ {i + 1, j} + \frac {p _ b} {p _ a + p _ b} f _ {i, j + i}
$$
考虑边界时，当 $i + j \ge n$ 时，只需要再有一个 b 即可完成，所以每次有 $\frac {p _ a} {p _ a + p _ b}$ 的期望使答案加 $1$ 。
即：
$$
\begin {aligned}
& \sum _ i ^ \infty (\frac {p _ a} {p _ a + p _ b}) ^ i \\
= & - \frac {\frac {p _ a} {p _ a + p _ b}} {\frac {p _ a} {p _ a + p _ b} - 1} \\
= & \frac {p _ a} {p _ b}
\end {aligned}
$$
但是 $f _ {0, 0}$ 转移时会形成环，注意到：
$$
f _ {0, 0} = \frac {p _ a} {p _ a + p _ b} f _ {1, 0} + \frac {p _ b} {p _ a + p _ b} f _ {0, 0}
$$
即
$$
f _ {1, 0} = f _ {0, 0}
$$
所以用 $f_{1, 0}$ 作为起点。
查看代码
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
| #include <cstdio>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar(x % 10 + '0');
}
const int N = 1e3 + 10, mod = 1e9 + 7;
int n, pa, pb, invab, invb, f[N][N];
int binpow (int b, int k = mod - 2)
{
int res = 1;
while (k)
{
k & 1 && (res = (LL)res * b % mod);
b = (LL)b * b % mod;
k >>= 1;
}
return res;
}
int dfs (int x, int y)
{
if (x + y >= n)
return (x + y + (LL)pa * invb % mod) % mod;
if (f[x][y])
return f[x][y];
return f[x][y] = ((LL)dfs(x + 1, y) * pa % mod + (LL)dfs(x, y + x) * pb % mod) * invab % mod;
}
int main ()
{
read(n), read(pa), read(pb);
invab = binpow(pa + pb), invb = binpow(pb);
write(dfs(1, 0));
return 0;
}
|