题目大意
输入 k pa pb
最初空字符串，每次增加一个字符 a 或者 b, 当子串ab的个数>=k就停止,求停止时 子串ab的个数的期望。
子串的不需要连续 比如aab 是有两个ab子串
产生a的概率为 pa/(pa+pb), 产生b的概率为 pb/(pa+pb)
期望 计算过程中 不使用小数，而是用 逆模
所有值模1000 000 007
数据范围
1<=pa pb<=1 000 000
1<=k<=1 000
解答
官方题解
意思是用dp[i][j] 表示前缀 中 有i个a ，j个ab子串的子串个数的期望值
用的是从长的推短的 反过来，首先如果 j>=k 那么 dp[i][j] = j
递推表达式 dp[i][j] = (pa * dp[i+1][j] + pb * dp[i][i+j])/(pa+pb)
也就是 根据最后一个字符来进行分化
所以最后的结果就是dp[0][0] = dp[1][0]
其中一些问题
虽然j>=k已经解决了 但是 i还是可以无限大，根据递推表达式 和 级数 的办法 可以求得dp[k][j] here
不用小数用逆模运算 wiki的最后一条
实现
我的代码
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
51
52
53
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}
ll mul_inv(ll a,ll b=MOD ){
ll matrix[3][2]={{a,b},{1,0},{0,1}};
int itr = 0;
while(matrix[0][itr^1] != 1){
ll t = matrix[0][itr]/matrix[0][1^itr] ;
rep(i,0,3)
matrix[i][itr] -= t * matrix[i][1^itr];
itr^=1;
}
return (matrix[1][itr^1] % b + b )%b;
}
int k;
ll dp[1010][1010] = {0};
ll getdp(int i,int j){
return j >= k? j : dp[i][j];
}
int main(){
ll a,b;
cin>>k>>a>>b;
rep(i,0,k)
dp[k][i] = (i + k + a * mul_inv(b)) % MOD;
int i,j;
for(i=k-1;i>=1;i--)
for(j=k-1;j>=0;j--){
dp[i][j] = (a*getdp(i+1,j) + b * getdp(i,i+j))%MOD;
dp[i][j] = (dp[i][j] * mul_inv(a+b))%MOD;
}
cout<<getdp(1,0)<<endl;
return 0;
}
|