[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)

发布于 2018-04-07  86 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)

Description

You are given three integers k, pa and pb.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability pa / (pa + pb), add 'a' to the end of the sequence. Otherwise (with probability pb / (pa + pb)), add 'b' to the end of the sequence.

You stop once there are at least k subsequences that form 'ab'. Determine the expected number of times 'ab' is a subsequence in the resulting sequence. It can be shown that this can be represented by P / Q, where P and Q are coprime integers, and . Print the value of .

Tag

动态规划

题目大意

随机生成一个只包含a和b的串,a和b分别有不同的生成期望,求当生成至少K个子序列ab时停止,求期望的ab的子序列个数。

解决思路

设\(F[i][j]\)表示生成了i个ab的子序列,当前接了j个a时,达到终止状态还要加的个数的期望,那么有转移方程
\[F[i][j]=F[i][j+1]*pa+F[i+j][j]*pb\]
但要注意的是,这个式子的前一项是可以无限展开的,其实际意义就是可以无限地在后面加a而不加b,这样就永远达不到子序列ab出现k次的要求,所以当i+j>=K的时候不能这么转移。
而i+j>=K的时候,只要再加一个b就会停止,我们把式子化出来看看
\[F[i][j]=pb(i+j)+pa*pb(i+j+1)+pa^2*pb(i+j+2)+……\]
\[pa*F[i][j]=pa*pb*(i+j)+pa^2*pb*(i+j+1)+pa^3*pb*(i+j+2)+……\]
\[(1-pa)*S=pb(i+j)+pb(pa+pa^2+pa^3+……)\]
里面是一个等比数列求和的形式,由于有pa < 1,所以运用等比数列求和公式得到
\[(1-pa)F[i][j]=pb(i+j)+pb*\frac{pa}{1-pa}\]
\[(1-pa)F[i][j]=pb(i+j)+pa\]
\[pb*F[i][j]=pb(i+j)+pa\]
\[F[i][j]=i+j+\frac{pa}{pb}\]
所以,当i+j>=K时,运用我们推出的式子直接计算;否则,动态规划计算。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int Mod=1e9+7;
const int inf=2147483647;

ll K,a,b;
ll F[maxN][maxN];

ll QPow(ll x,ll cnt);

int main()
{
    ios::sync_with_stdio(false);
    cin>>K>>a>>b;
    ll invab=QPow(a+b,Mod-2);
    ll inva=QPow(a,Mod-2),invb=QPow(b,Mod-2);
    for (int i=K;i>=0;i--)
        for (int j=K;j>=0;j--)
            if ((i!=0)||(j!=0))
            {//分情况讨论
                if (i+j>=K) F[i][j]=(ll)(i+j)+(ll)a*invb%Mod;
                else F[i][j]=((ll)a*F[i][j+1]%Mod*invab%Mod+(ll)b*F[i+j][j]%Mod*invab%Mod)%Mod;
            }
    cout<<F[0][1]<<endl;
    return 0;
}

ll QPow(ll x,ll cnt)
{
    ll ret=1;
    while (cnt)
    {
        if (cnt&1) ret=ret*x%Mod;
        x=x*x%Mod;
        cnt=cnt>>1;
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)


HNCJ OIer 一枚