Codeforces908D New Year andArbitrary Arrangement-dp

传送门
题意：

给出 k,p1,p2 ，一开始串为空，每次有 p1p1+p2 的概率在串中加一个a， p2p1+p2 的概率在串中加一个b，当串中有k个为ab的子序列停止加字符，求停止加字符后串中为ab的子序列的个数的期望，假设结果为最简分数 ans1ans2 ,输出 ans1∗ans−12mod(1e9+7) 。

Solution：

明显是一道dp题，因为长度可以无穷大，所以说我们需要考虑如何才能限制住“无穷大”，我们发现，如果我们加了一个b，ab的增加量为当前串中a的个数，所以说我们可以用一个状态 f[i][j] 表示在串中有i个a，j个ab时开始加字符直到停止的期望ab个数，转移很显然:

f [i] [j] = p 1 * f [ i + 1 ] ] [ j ] + p 2 * f [ i ] [ i + j ] p 1 + p 2

那么我们最后的答案应为 f[1][0] ,因为在第一个a出现之前，无论有多少b，ab数量都不会变与，只有当出现第一个a时，我们加入b才会产生ab

那么我们开始考虑临界状况：

首先有一个显然的状态： f[i][j]=j(j>=k)

其次我们考虑的就是 i+j>=k 的情况：在这种情况下，只要出现一个b，就会停止加字符，所以说我们只需要考虑再连续加a的个数的期望：（方便考虑我们设 P=p2p1+p2 ）

加入n个a再加入一个b的概率为： (1−P)n∗P

所以说再连续加a的个数的期望为:

ans=∑∞i=0(1−P)i∗P∗i

=P∑∞i=0(1−P)i∗i

设 x=1−P

ans=P∑∞i=0xi∗i

设 S=∑∞i=0xi∗i=0+x+2∗x2+...

运用错位相减法， xS=x2+2∗x3+...

(1−x)S=x+x2+x3+...=x−x∞x1−x=x1−x

S=x(1−x)2

ans=P∗S=P∗(1−P)P2=1−PP

那么我们的另一个临界状态也就出来了： f[i][j]=1−PP(i+j>=k)

然后这道题就华丽丽的做完了~

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int k,pa,pb;
int f[1010][1010];
const int mod=1e9+7;
int fast_pow(int x,int a)
{
    int ans=1;
    for (;x;x>>=1,a=1ll*a*a%mod)
        if (x&1) ans=1ll*ans*a%mod;
    return ans;
}
int inv(int x)
{
    return fast_pow(mod-2,x);
}
int dp(int x,int y)
{
    if (y>=k) return y;
    return f[x][y];
}
int main()
{
    scanf("%d%d%d",&k,&pa,&pb);
    for (int i=0;i<k;i++)
        f[k][i]=(1ll*k+i+1ll*pa*inv(pb))%mod;
    for (int i=k-1;i;i--)
        for (int j=k-1;j>=0;j--)
        {
            f[i][j]=(1ll*dp(i+1,j)*pa+1ll*dp(i,j+i)*pb)%mod;
            f[i][j]=1ll*f[i][j]*inv(pa+pb)%mod;
        }
    printf("%d",f[1][0]);
}