刚学OI，不知道这个是否正确

根据CF908D改了一下（原题是子序列）

给定3个数字，k，pa,pb

每次有

\frac{pa}{pa + pb}

的概率往后添加一个 a

每次有

\frac{pb}{pa + pb}

的概率往后添加一个 b

当出现了

k

个形如 ab 的子串时停止。

求出所需步数的期望数。

答案对 1e9 + 7 取模。

目前我的思路是：

f[i][0 / 1]

当前已经有了

i

个子串，当前字符为

a \space or \space b

。

f[i][0] = f[i + 1][1] + \frac{pa + pb}{pb} \\ f[i][1] = f[i][0] + \frac{pa + pb}{pa}

然后倒着逆推。

第一个递推式：

f[i][0] = (f[i][0] + 1) \times \frac{pa}{pa + pb} + (f[i + 1][1] + 1)\frac{pb}{pa + pb}

化简之后

f[i][0] = f[i + 1][1] + \frac{pa + pb}{pb}

第二个递推式：

f[i][1] = (f[i][1] + 1) \times \frac{pb}{pa + pb} + (f[i][0] + 1) \times \frac{pa}{pa + pb}

化简之后

f[i][1] = f[i][0] + \frac{pa + pb}{pa}

CPP

#include <bits/stdc++.h>
#define int long long
inline int rd(void) {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') ch = getchar(); }
    while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
inline void wt(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wt(x / 10);
    putchar(x % 10 + 48); 
}
using db = double;
const int N = 1e3, MOD = 1e9 + 7;
inline int qmi(int a, int b)
{
    int ans = 1;
    while (b) { if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; }
    return ans;
}
int f[N][N];
auto main() -> signed
{
    int k = rd(), pa = rd(), pb = rd();
    int p0 = qmi(pa, MOD - 2) * (pa + pb) % MOD, 
        p1 = qmi(pb, MOD - 2) * (pa + pb) % MOD;
    for (int i = k - 1; i >= 0; i -- )
    {
        f[i][0] = f[i + 1][1] + p1;
        f[i][1] = f[i][0] + p0;
    }
    std::cout << f[0][1] + f[0][0] << std::endl;
    return 0;
}

刚学OI，不知道这个是否正确

讨论操作

回复

相关推荐

刚学OI，不知道这个是否正确