codeforces 908d New Year and Arbitrary Arrangement

codeforces 908d New Year and Arbitrary Arrangement

(​​are given three integers k, pa and pb.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability pa / (pa + pb), add ‘a’ to the end of the sequence. Otherwise (with probability pb / (pa + pb)), add ‘b’ to the end of the sequence.

You stop once there are at least k subsequences that form ‘ab’. Determine the expected number of times ‘ab’ is a subsequence in the resulting sequence. It can be shown that this can be represented by P / Q, where P and Q are coprime integers, and . Print the value of . Input

The first line will contain three integers integer k, pa, pb (1 ≤ k ≤ 1 000, 1 ≤ pa, pb ≤ 1 000 000). Output

Print a single integer, the answer to the problem. Examples Input

1 1 1

Output

2

Input

3 1 4

Output

370000006

Note

The first sample, we will keep appending to our sequence until we get the subsequence ‘ab’ at least once. For instance, we get the sequence ‘ab’ with probability 1/4, ‘bbab’ with probability 1/16, and ‘aab’ with probability 1/8. Note, it’s impossible for us to end with a sequence like ‘aabab’, since we would have stopped our algorithm once we had the prefix ‘aab’.

The expected amount of times that ‘ab’ will occur across all valid sequences is 2.

For the second sample, the answer is equal to .

哇给icefox 大佬跪烂键盘啊 这个公式我一开始根本就理解不了

此题给的是一开始一个空序列 然后每次可以往后面添加pa/(pa+pb)概率的a 或者是可以添加pb/(pa+pb)概率的b 然后一共你需要构成K个ab的子序列一旦构成k个了 那么就停止 现在你需要求一下这个给定pa pb需要求一下这个空串未来的期望 好怎么搞 设dp[i][j]表示我现在前缀有i个a字母和j个ab子串 那么简单来看会有一个转移

dp[i][j]=pa/(pa+pb)*dp[i+1][j]+pb/(pa+pb)*dp[i][i+j]

有了这个式子 但是我们不能够去写代码 为什么 因为这个a会无限递增下去 同时如果我i+j>=k的时候我也不能够一直做下去了 因为我有很多情况 我可以一直添加a导致不能停止

那怎么办我把这个单独的提出来

设现在i+j>=k了 那么我手动去算一下他的期望是多少 发现是可以算的

我们设这个期望是

ans=pbpa+pb∗∑infj=0(papa+pb)j∗(k+j)哇顺带学一学latex qwq 蒟蒻的颓废之旅 大概这个式子 我们可以不停的往里去迭代下去 然后可以发现这是 一个等比数列 然后怎么办 这个等比数列 还有系数 但是系数是递增的我从第一项开始 把每个后面的都提出第一个系数这么多的后面的项 然后 发现第一个被我提没了 继续提第二个 这样又发现是一个等比数列 好了写出通项ans=k+papb即 =i+j+papb 直接dp即可 最后还有一个问题 在我第一a出现之前我可能有很多很多个b 但是我们知道这些b是对答案没有贡献的 dp[0][0]=(pa∗dp[1][0]+pb∗dp[0][0])/(pa+pb)

dp[0][0]就等于dp[1][0]!所以答案就是dp[1][0]即可。

#include#define ll long long#define mod 1000000007ll k,pa,pb,dp[1100][1100];int main(){ freopen("cf.in","r",stdin); scanf("%lld%lld%lld",&k,&pa,&pb); ll invb=1,base=pb;for (int t=mod-2;t;t>>=1,(base*=base)%=mod) if (t&1) (invb*=base)%=mod; ll inva_b=1;base=pa+pb;for (int t=mod-2;t;t>>=1,(base*=base)%=mod) if (t&1) (inva_b*=base)%=mod; ll invab=pa*invb%mod;pa*=inva_b;pa%=mod;pb*=inva_b;pb%=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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。