cf908DNew Year and Arbitrary Arrangement

与天地兮比寿，与日月兮齐光。这篇文章主要讲述cf908DNew Year and Arbitrary Arrangement相关的知识，希望能为你提供帮助。
1.??题目链接??。题目大意，给定k,a,b.现在构造一个字符串，每个位置有两种选择，a/(a+b)概率会选择a,b/(a+b)会选择b.当ab这个子序列出现的次数大于等于k次之后就停止构造，问ab这个子序列出现的期望次数。
2.还是比较有意思的一道题目，还是求期望，那么一般还是倒着dp.dp[i][j]表示出现了i个a,j个ab子序列的期望。倒着考虑时，转移式很好推出来。
dp[i][j]=dp[i][j]+pa/(pa+pb)*dp[i+1][j]+pb/(pa+pb)*dp[i][i+j].
解释一下这个dp式子，在倒着考虑时，如果当前为是a,那么等于i+1个a并且j个ab转移过来，如果当前字符是b,那么就对答案有贡献了，前面的所有的a都会和这个b组合，产生i个ab.那么就会从i转移过来。这是一个人人为我的dp。最后考虑到起点就是答案。但是有两种特例：
(1)bbbbbbbbabbbbb这种，前边有很多b，因为a不存在，所以b没有。这个时候dp[1][0]=dp[0][0]就是答案。
(2)aaaaaaaaaa.....b.有无限多个a,这时一旦出现一个b,就会产生很大的贡献，立刻就满足条件了，但是i+k这个时候大于k，这个状态就没办法再从前边推出来，这个可以手算一下，是一个差比数列（等差数列和等比梳理的复合）。计算一下可以得到:
dp[i][j]=i+j+pa/pb.
然后这个题就做完了。

#include< bits/stdc++.h>
#define ll long long
#define mod 1000000007
ll k, pa, pb, dp[1100][1100];
ll qpow(ll a, ll b)
ll res = 1;
while (b)
if (b & 1)res = res * a%mod;
a=a*a%mod;
b > > = 1;

return res;

int main()
scanf("%lld%lld%lld", & k, & pa, & pb);
ll ca = pa, cb = pb;
ll invab = pa * qpow(cb, mod - 2) % mod;
pa = pa * qpow(ca + cb, mod - 2)%mod;
pb = pb * qpow(ca + cb, mod - 2)%mod;
for (int i = k; ~i; --i)
for (int j = k; ~j; --j)
if (i + j > = k) dp[i][j] = (i + j + invab) % mod;
else dp[i][j] = pa * dp[i + 1][j] % mod + pb * dp[i][i + j] % mod, dp[i][j] %= mod;
printf("%lld", dp[1][0]);
return 0;