CF 908D New Year and Arbitrary Arrangement

题目描述

https://codeforces.com/problemset/problem/908/D

Solution

我们考虑令 $f[i][j]$ 表示有 $i$ 个 $a$，其中 $ab$ 的子序列有 $j$ 个的期望

显然有 $f[i][j]=pa\times f[i+1][j]+pb\times f[i][i+j]$，其中 $pa$ 和 $pb$ 分别为选 $a$ 和选 $b$ 的概率

那么我们有 $f[i][j]=j$，其中 $j$ 大于等于 $k$

但是我们发现这样的 $i$ 的长度可以是无限大的

所以我们换一个终止状态，我们令 $f[i][j]=pb\sum_{k=0}^{\infty} pa^i (i+j+k)$，其中 $i+j\ge k$

即对于 $i+j\ge k$ 的状态，只要出线一次 $b$ 就 $ok$ 了，然后这个无穷级数的答案是 $\frac{pa}{pb}$，此处的 $pa$ 和 $pb$ 是题目输入的 $pa$ 和 $pb$

另外注意到 $f[0][0]$ 等于 $f[1][0]$

#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 1010
#define ll long long 
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s;
}

int n;
ll pa, pb, pc; 

ll f[maxn][maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int x, y; cin >> n >> x >> y;
    pa = x * pow_mod(x + y, p - 2) % p; 
    pb = y * pow_mod(x + y, p - 2) % p;
    pc = x * pow_mod(y, p - 2) % p; 
    for (int i = n; i; --i)
        for (int j = n; ~j; --j)
            f[i][j] = i + j >= n ? (i + j + pc) % p : (pa * f[i + 1][j] + pb * f[i][i + j]) % p;
    cout << f[1][0] << "\n"; 
    return 0;
}