题解 | #New Year and Arbitrary Arrangement#

【New Year and Arbitrary Arrangement】

定义$dp(i,j)dp(i,j)$为子序列"ab"的个数为$ii$且存在$jj$个"a"时的期望。

状态转移为：

特殊的，当$i=0,j=0i=0,\; j=0$时：

如果我一直不选"b"，那么$dp(i,j)dp(i,j)$的$jj$就会增大到无限，这显然是不行的。

当$i+j\ge ki+j\backslash ge\; k$时，只要选取一个"b"，就能到达末态:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;

ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

ll inv(ll x) { return power(x, mod - 2); }

ll k, pa, pb, dp[N][N];
ll res = 0;
int main() {
    cin >> k >> pa >> pb;
    ll qa = pa * inv((pa + pb) % mod) % mod;
    ll qb = pb * inv((pa + pb) % mod) % mod;
    for (int i = k - 1; i >= 0; i--) {
        for (int j = k; j >= 1; j--) {
            if (i + j >= k)
                dp[i][j] = ((i + j) % mod + pa * inv(pb) % mod) % mod;
            else
                dp[i][j] =
                    (qb * dp[i + j][j] % mod + qa * dp[i][j + 1] % mod) % mod;
        }
    }
    dp[0][0] = dp[0][1];

    cout << dp[0][0];
    return 0;
}