Codeforce problem 908 D. new year and arbitrary arrangement (probability DP)

Topic link ：Problem - 908D - Codeforces

The question ： Given three integers k,pa,pb, The string is empty at first , Every time pa/(pa+pb) The probability of adding a to the end of the string a, Yes pb/(pa+pb) The probability of adding a to the end of the string b, When in the string ab The number of subsequences of is greater than or equal to k Stop adding characters when , Ask the string after stopping adding characters ab The expectation of the number of subsequences . Generally, it is the simplest fraction ans1/ans2, Output ans1 multiply ans2 About mod Re pairing of inverse elements of mod modulus .mod by 1e9+7

analysis ： set up f[i][j] Indicates that there is i individual a,j individual ab Add characters to the subsequence until it stops ab The expectation of the number of subsequences .

So obviously there is f[i][j]=j(j>=k), The dynamic transfer equation is also relatively simple , Namely ：

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

When we add a to the original string a when , The impact on the original string is only a Add the number of 1, It will not affect the original string ab The number of subsequences affects , When we add a to the original string b when , In the original string a The number of does not affect , But how many in the original string a, Then add with the current operation b After the combination, there will be several more ab Subsequence , This is the origin of the dynamic transfer equation .

But we can easily find a problem , That is, if the string has been added a, Then it won't stop at all , So we still need to calculate by hand a Especially in many cases ：

When a The number of +ab The number of subsequences is greater than or equal to k when , Now we only need to choose one of the following character selections b, Then we can meet the meaning of the topic , So we can calculate the expected value in this case by hand .

set up p1=pa/(pa+pb)  p2=pb/(pa+pb)

Let's say that the first k I chose one at the time b, Then the probability of this happening is

p1^(k-1)*p2, In this case, finally ab The number of subsequences is |a|+(k-1)+|ab|, So the expectation is

Our target state is f[1][0], Because there must be one first a It's possible that ab Subsequence , So we can output directly f[1][0], If we output f[0][0] There will be a problem , Because in （0,0） The state may also transition to （0,0） state , This will recurse infinitely and will never satisfy the recursion termination condition , So we should output f[1][0].

Here is the code ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e3+10,mod=1e9+7;
long long qpow(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
long long pa,pb,k,ni;
long long f[N][N];//f[i][j] Indicates that the current status has i individual a,j individual ab The expectation of adding characters to a subsequence until it stops ab Number 
long long dfs(long long x,long long y)//X Represents the current state a The number of ,y Represents the current state ab The number of subsequences  
{
	if(x+y>=k) return (x+y-1+(pa+pb)*qpow(pb,mod-2))%mod;
	if(f[x][y]>0) return  f[x][y];
	f[x][y]=(f[x][y]+pa*ni%mod*dfs(x+1,y))%mod;
	f[x][y]=(f[x][y]+pb*ni%mod*dfs(x,x+y))%mod;
	return f[x][y];
}
int main()
{
	cin>>k>>pa>>pb;
	ni=qpow(pa+pb,mod-2);
	printf("%lld",dfs(1,0));
	return 0;
}