CF908D New Year and Arbitrary Arrangement

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 \geq 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}$ 作为起点。

查看代码

#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;
}