Solvution

题意是每一次操作有的概率在已有序列中加入'a',有的概率加入'b',求一个序列中有k个'ab'子序列(不连续)的期望步数。
考虑dp,设表示这个序列中有个'a'字符和个'ab'串,转移显然分别是考虑生成'a'和'b'的情况
关键是边界的处理,发现可能会出现无限的序列,但是对于无限的序列的期望值是可以计算的。在的情况下,如果说再往后加很多'a'和1个'b'时,期望值为
确实是一道好题,但是我感觉放在D这个位置对我这种弱菜选手就比较不友善了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000 + 5 , Mod = 1e9 + 7;
namespace Math
{
    inline LL mul(LL x , LL y)
    {
        LL ans = 0;
        while(y)
        {
            if(y & 1) ans = (ans + x) % Mod;
            x = (x << 1) % Mod;
            y >>= 1;
        }
        return ans;
    }
    inline LL pow(LL x , LL y)
    {
        LL ans = 1;
        while(y)
        {
            if(y & 1) ans = mul(ans , x);
            x = mul(x , x);
            y >>= 1;
        }
        return ans;
    }
    inline LL inv(LL x){ return pow(x , Mod - 2);}
}
using namespace Math;
LL k , pa , pb , isum;
LL dp[N][N];
LL solve(int n , int m)
{
    if(m >= k) return m;
    if(n == k)
    {
        LL sum = (1 - pb + Mod) % Mod;
        LL ipb = inv(pb);
        return (mul(sum , ipb) + m + n) % Mod;
    }
    if(dp[n][m] != -1) return dp[n][m];
    LL& res = dp[n][m];
    res = (mul(pa , solve(n + 1 , m)) + mul(pb, solve(n , n + m))) % Mod;
    return res;
}
int main()
{
    scanf("%I64d%I64d%I64d" , &k , &pa , &pb);
    memset(dp , -1 , sizeof dp);
    isum = inv(pa + pb);
    pa = mul(pa , isum) , pb = mul(pb , isum);
    printf("%I64d\n" , solve(1 , 0));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注