牛客周赛--round 80--G题--dp+逆元
链接：https://ac.nowcoder.com/acm/contest/101196/G
来源：牛客网

题目描述

小红和小紫正在对弈。在围棋规则中，每吃掉对方的一枚棋子，就需要将这枚棋子放入棋盖中。然而，棋盖空间不大，她们任何一方吃子数量达到 x 就输了。
当然，我们不需要考虑具体的对弈局面，模型简化如下，每个回合将会依次执行以下两步：
小红有 p1 的概率吃掉对方一枚棋子；
小紫有 p2 的概率吃掉对方一枚棋子。
谁吃子数量达到 x 就输了。小红执黑先手，她想知道自己最终获胜的概率是多少？你需要将答案对 (10^9+7) 取模后输出。

输出描述

输出概率的逆元表示

题型

动态规划(dp)+逆元

思路

先看状态转移方程：，最后答案求dp[0][0]（注：下面的分母(1-(1-p1)*(1-p2))，用(p1+p2)-p1*p2是完全一样的）
下面是推导过程
设小红为A，小紫为B，p1=a1/b1，p2=a2/b2
设dp[i][j]为A放第i个子，B放第j个子时的概率
可以发现，每一次下棋都会出现四种情况(A吃/不吃，B吃/不吃)，由于A不吃且B不吃（即(1-p1)*(1-p2)）的情况对于过程没有任何贡献，故无需考虑
1.A吃/B吃（p1*p2）：发现其对于i的贡献是+1,对于j的贡献也是+1
2.A吃/B不吃（p1*(1-p2)）：发现其对于i的贡献是+1,对于j的贡献是0
3.A不吃/B吃（(1-p1)*p2）：发现其对于i的贡献是0,对于j的贡献是+1
把上面三项相乘再相加，再除以三项总概率的逆元，即为dp[i][j]，由此，上面的公式就推导出来了

注意点

1.注意初始化，即dp[x][i]=0，dp[i][x]=1，（i=0~x-1（不是x!））(x为输入的吃子限定数量，因为A下了x个子A就输了，B下了x个子A就赢了)
2.注意最后求的是dp[0][0]，并且由于前面的p1,p2已经是逆元表示了，所以求出的dp[0][0]也已经是逆元表示了，不需要再求逆元了
3.注意取模不要漏了，以及如果有减号的地方，后面最好加一个MOD再取余，防止出现负数

代码 

#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=1e3+200;
int MOD=1e9+7;
int dp[N][N];
int qpow(int a,int b,int p){
	int tmp=1;
	a%=p;
	while(b){
		if(b&1) tmp=tmp*a%p;
		a=a*a%p;
		b>>=1;
	}
	return tmp%p;
}
int inv(int a,int p){ //求a的逆元(1/a) 
	return qpow(a,p-2,p)%MOD;
}
signed main(){
	int n,a,b,a2,b2,x,y;
	scanf("%lld",&n);
	scanf("%lld%lld%lld%lld",&a,&b,&a2,&b2);
	x=a*inv(b,MOD)%MOD;
	y=a2*inv(b2,MOD)%MOD;
	for(int i=0;i<=n-1;i++){
		dp[n][i]=0;
		dp[i][n]=1;
	}
	int xx=(1LL+MOD-x)%MOD,yy=(1LL+MOD-y)%MOD;//xx=1-x,yy=1-y;
	for(int i=n-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			dp[i][j]=(1LL*inv((1LL-(xx*yy)%MOD+MOD)%MOD,MOD)%MOD*(x*yy%MOD*dp[i+1][j]%MOD+xx*y%MOD*dp[i][j+1]%MOD+x*y%MOD*dp[i+1][j+1]%MOD)%MOD)%MOD;
		}
	}
	printf("%lld\n",(dp[0][0]+MOD)%MOD);
	return 0;
}