Codeforces -908D

发表于 | 分类于 | 浏览 次

题解

$dp[i][j]$表示有$i$个$a$,j个ab时的期望，可得转移方程
$$
dp[i][j]={dp[i+1][j]\times pa +\\
dp[i][j+i]\times pb}
$$
(注意这里需要求的是期望，当前状态的期望由它可能到达的状态求得，而不是能到达它的状态求得)
当$i+j>=k$时，只要末尾中再出现一个$b$，此时的ab子序列个数就变成了$i+j$个，而$i+j>=k$，满足了题目条件。当末尾得到一个$a$时，继续添加，当得到一个$b$时，添加的过程停止。因此当停止时添加的字符个数（包括最后一个$b$）的期望为$1\over pb$（每次有pb的概率停止，那么使过程停止的期望次数是$1\over pb$。类似一个人投篮，每次有$p={2\over 3}$的概率投中，那他投中一次的所需要的投篮次数的期望为${1\over p}=1.5$次），$1\over pb$个字符中，1个b，${1\over pb}-1$个a，则等于增加了${1\over pb}-1={ {1-pb}\over pb}={pa\over pb}$个$ab$子序列
因此可以得出总的方程
$$
\begin{cases}
dp[i][j]={dp[i+1][j]\times pa +\\ dp[i][j+i]\times pb} & i+j<k \\
dp[i][j]=i+j+{pa\over pb} & i+j\ge k
\end{cases}
$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include "stdio.h"
#include "cstring"
#include "stdlib.h"
#include "map"
#include "string"
#include "iostream"
#include "set"
#include "queue"
#include "list"
#include "vector"
#include "algorithm"
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
using namespace std;
typedef long long ll;
const ll MAXN=2e3+100;
const ll MOD=1e9+7;

void exgcd(ll a,ll b,ll& d,ll& x,ll& y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}

ll inv(ll a) //a 关于 mod MOD除法的逆元
{
    ll d, x, y;
    exgcd(a, MOD, d, x, y);
    return d == 1 ? (x+MOD)%MOD : -1;
}
ll dp[MAXN][MAXN];
int main(int argc, char const *argv[]) {
    ll n,n1,n2;
    cin>>n>>n1>>n2;
    ll pa=n1*inv(n1+n2)%MOD;
    ll pb=n2*inv(n1+n2)%MOD;
    ll pbi=inv(pb);
    // ll ans=0;
    Met(dp,0);
    for(int i=n;i>0;--i)
    {
        for(int j=n-i;j>=0;--j)
        {
            if(i+j==n) dp[i][j]=(i+j+pa*pbi)%MOD;
            else dp[i][j]=(dp[i+1][j]*pa%MOD + dp[i][j+i]*pb%MOD)%MOD;
        }
    }
    cout<<dp[1][0]<<endl;
    return 0;
}