Codeforces 908D New Year and Arbitrary Arrangement

题目链接http://codeforces.com/contest/908/problem/D

题意:有一个ab字符串,初始为空。用\frac{p_a}{p_a+p_b}的概率在末尾添加字母a,有\frac{p_b}{p_a+p_b}的概率在末尾添加字母b,当出现≥kab子串时立即停止添加字母,求最后期望的ab子串个数。(子串ab不要求连续)。

思路https://blog.csdn.net/can919/article/details/78940673

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int P=1e9+7;
const int N=2000+10;
int k,i,j,pa,pb,inv,inv2,dp[N][N];
int fexp(int a,int n){
    int res=1;
    while (n){
        if (n&1) res=1LL*res*a%P;
        a=1LL*a*a%P;
        n>>=1;
    }
    return res;
}
int main(){
    read(k),read(pa),read(pb);
    inv=fexp(pb,P-2),inv2=fexp(pa+pb,P-2);
    for (i=k;i>=1;--i){
        for (j=k;j>=0;--j){
            if (i+j>=k) dp[i][j]=(i+j+1LL*pa*inv)%P;
            else dp[i][j]=(1LL*pa*dp[i+1][j]%P+1LL*pb*dp[i][i+j]%P)*inv2%P;
        }
    }
    printf("%d\n",dp[1][0]);
    return 0;
}

发表评论

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