Codeforces908D New Year andArbitrary Arrangement-dp

传送门
题意：

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

Solution：

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

f[i][j]=p1∗f[i+1]][j]+p2∗f[i][i+j]p1+p2 $$f[i][j]=\frac{p_1\ast f[i+1]][j]+p_2\ast f[i][i+j]}{p_1+p_2}$$

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

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

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

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

加入n个a再加入一个b的概率为： (1−P)n∗P $(1-P{)}^n\ast P$

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

ans=∑∞i=0(1−P)i∗P∗i $ans=\underset{i=0}{\overset{\infty }{\sum }}(1-P{)}^i\ast P\ast i$

=P∑∞i=0(1−P)i∗i $=P\underset{i=0}{\overset{\infty }{\sum }}(1-P{)}^i\ast i$

设 x=1−P $x=1-P$

ans=P∑∞i=0xi∗i $ans=P\underset{i=0}{\overset{\infty }{\sum }}{x}^i\ast i$

设 S=∑∞i=0xi∗i=0+x+2∗x2+... $S=\underset{i=0}{\overset{\infty }{\sum }}{x}^i\ast i=0+x+2\ast x^2+...$

运用错位相减法， xS=x2+2∗x3+... $xS=x^2+2\ast x^3+...$

(1−x)S=x+x2+x3+...=x−x∞x1−x=x1−x $(1-x)S=x+x^2+x^3+...=\frac{x-x^{\infty }x}{1-x}=\frac{x}{1-x}$

S=x(1−x)2 $S=\frac{x}{(1-x{)}^2}$

ans=P∗S=P∗(1−P)P2=1−PP $ans=P\ast S=P\ast \frac{(1-P)}{P^2}=\frac{1-P}{P}$

那么我们的另一个临界状态也就出来了： f[i][j]=1−PP(i+j>=k) $f[i][j]=\frac{1-P}{P}(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]);
}