打一局吗
题目描述
Diaoyeye 作为健美先生，自然会受到很多人的挑战，nyx 便是他们中的一位。 nyx 具有自知之明，他知道 Diaoyeye 比他健美的多，和他刚正面显然不行，于是 要求 Diaoyeye 和他打牌。
nyx 制定的游戏规则是这样的：一副只有黑白两种颜色的牌，从背面看都是一样， 两个人轮流取牌堆顶的一张牌，如果谁先取到了黑色牌谁就获胜。同时 nyx 还请了 pupil 来捣乱，pupil 会在两个人取完牌后把牌堆顶的一张牌拿走，但是不会给 nyx 和 Diaoyeye，不论pupil 这张牌是黑色牌还是白色牌，都把它作废。所以有可能 nyx 和 Diaoyeye 都没有抽到黑色牌，判为平局。
nyx 通过一些手段知道了牌堆里黑色牌和白色牌的数量，然后他想知道先手获胜概率和后手获胜概率，然后考虑是不是快点投降。
输入描述
输入包括一行，两个正整数 \(a\)，\(b\)，表示黑色牌和白色牌的数量。
输出描述
输出包括两个整数，用空格隔开，分别表示先手获胜的概率和后手获胜的概率，用乘法逆元的形式输出，对 \(1004535809\) 取模。
输入输出样例 #1
样例输入 #1
1 3
样例输出 #1
502267905 753401857
输入输出样例 #2
样例输入
3 1
样例输出
251133953 753401857
说明/提示
样例#1解释
先手取到黑色牌，先手赢。
先手取到白色牌，后手取到黑色牌，后手赢。
先手取到白色牌，后手取到白色牌，pupil取到白色牌，先手取到黑色牌，先手赢。
先手取到白色牌，后手取到白色牌，pupil取到黑色牌，先手取到黑色牌，平局。
先手获胜的概率是0.5，取模之后是502267905。
后手获胜概率是0.25，取模之后是753401857。
数据范围和约定
对于 \(20\)% 的数据，\(1\leq a,b\leq 10\)。
对于 \(60\)% 的数据，\(1\leq a,b\leq 2000\)。
对于 \(100\)% 的数据，\(1\leq a,b\leq 10000\)。
有关数学公式
若 \(p\) 为质数，则 \(\forall a \in \N_+\)，\(a^{p-1} \equiv 1 \pmod{p}\)。
解题报告
好吧，一道基础的概率 DP，但是需要一些优化的技巧。
我们对先手和后手分别计算，设 \(i\) 表示黑牌的个数，\(j\) 表示白牌的个数，\(f_{i,j}\) 表示先手获胜概率，\(g_{i,j}\) 表示后手获胜概率。
随带一提，一开始用记忆化搜索的思路常常会好想很多。
对于先手获胜，有以下情况：
- 若 \(i \geq 1\)，先手摸到黑牌，概率 \(\dfrac {i}{i+j}\)。
- 若 \(j\geq3\)，先手摸到白牌，后手摸到白牌，第三者摸到白牌，概率 \(\dfrac{j}{i+j} \times \dfrac{j-1}{i+j-1} \times \dfrac{j-2}{i+j-2} \times f_{i,j-3}\) 。
- 若 \(j \geq 2\)，先手摸到白牌，后手摸到白牌，第三者摸到黑牌，概率 \(\dfrac{j}{i+j} \times \dfrac{j-1}{i+j-1} \times \dfrac{i}{i+j-2} \times f_{i-1,j-2}\) 。
对于后手获胜，有以下情况：
- 若 \(i \geq 1,j\geq 1\)，先手摸到白牌，后手摸到黑牌，概率 \(\dfrac{j}{i+j} \times \dfrac{i}{i+j-1}\)。
- 若 \(j\geq3\)，先手摸到白牌，后手摸到白牌，第三者摸到白牌，概率 \(\dfrac{j}{i+j} \times \dfrac{j-1}{i+j-1} \times \dfrac{j-2}{i+j-2} \times g_{i,j-3}\) 。
- 若 \(j \geq 2\)，先手摸到白牌，后手摸到白牌，第三者摸到黑牌，概率 \(\dfrac{j}{i+j} \times \dfrac{j-1}{i+j-1} \times \dfrac{i}{i+j-2} \times g_{i-1,j-2}\) 。
dp 转移到这就完了，以下是用记忆化搜索实现的无逆元的版本：
double dfsF(int x,int y)
// 先手胜率
{if(f[x][y]==-1) return f[x][y];if(!x) return 0; // 没有黑了，平局if(x && !y) return 1; // 只有黑了，必赢f[x][y]=(double)x/(x+y);// 先后手都抽到白if(y>=2){double tmp=( (double)y/(x+y) )*( (double)(y-1)/(x+y-1) );// 先后手都抽到白的概率，枚举第三者的抽牌可能if(y>=3) f[x][y]+=tmp*dfsF(x,y-3)*( (double)(y-2)/(x+y-2) ); // 白if(x>=1) f[x][y]+=tmp*dfsF(x-1,y-2)*( (double)x/(x+y-2) ); // 黑}return f[x][y];
}double dfsG(int x,int y)
// 后手胜率
{if(g[x][y]==-1) return g[x][y];if(!x) return 0; // 没有黑了，平局if(x && !y) return 0; // 只有黑了，必输g[x][y]=( (double)y/(x+y) )*( (double)x/(x+y-1) );// 先手抽到白的同时，后手抽到黑if(y>=2)// 先后手都抽到白{double tmp=( (double)y/(x+y) )*( (double)(y-1)/(x+y-1) );// 先后手都抽到白的概率，枚举第三者的抽牌可能if(y>=3) g[x][y]+=tmp*dfsG(x,y-3)*( (double)(y-2)*(x+y-2) ); // 白if(x>=1) g[x][y]+=tmp*dfsG(x-1,y-2)*( (double)x/(x+y-2) ); // 黑}return g[x][y];
}
但是，这题要求逆元，所以我们要将所有的除法改成乘上逆元的形式。
用线性递推的方法求出需要的所有逆元就好了，为什么这要写是对的，我也不知道（doge）。
inline void GetInv(int n)
{inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}int dfsF(int x,int y)
// 先手胜率
{if(f[x][y]!=-1) return f[x][y];if(!x) return 0; // 没有黑了，平局if(x && !y) return 1; // 只有黑了，必赢f[x][y]=x*inv[x+y]%mod;// 先后手都抽到白if(y>=2){int tmp=( y*inv[x+y]%mod )*( (y-1)*inv[x+y-1]%mod )%mod;// 先后手都抽到白的概率，枚举第三者的抽牌可能if(y>=3) f[x][y]=( f[x][y]+tmp*dfsF(x,y-3)%mod*( (y-2)*inv[x+y-2]%mod )%mod )%mod; // 白if(x>=1) f[x][y]=( f[x][y]+tmp*dfsF(x-1,y-2)%mod*( x*inv[x+y-2]%mod )%mod )%mod; // 黑}return f[x][y]%mod;
}int dfsG(int x,int y)
// 后手胜率
{if(g[x][y]!=-1) return g[x][y];if(!x) return 0; // 没有黑了，平局if(x && !y) return 0; // 只有黑了，必输g[x][y]=( y*inv[x+y]%mod )*( x*inv[x+y-1]%mod )%mod;// 先手抽到白的同时，后手抽到黑if(y>=2)// 先后手都抽到白{int tmp=( y*inv[x+y]%mod )*( (y-1)*inv[x+y-1]%mod )%mod;// 先后手都抽到白的概率，枚举第三者的抽牌可能if(y>=3) g[x][y]=( g[x][y]+tmp*dfsG(x,y-3)%mod*( (y-2)*inv[x+y-2]%mod )%mod )%mod; // 白if(x>=1) g[x][y]=( g[x][y]+tmp*dfsG(x-1,y-2)%mod*( x*inv[x+y-2]%mod )%mod )%mod; // 黑}return g[x][y]%mod;
}这个时候，程序的正确性就有保证了，但是，这题的 \(a\)、\(b\) 可以达到 \(10000\)，数组开不下，时间复杂度也无法接受！！！
怎么办？
一个常用的方法：用循环数组。这是由于我们发现：关于 \(i\) 的一维只会由 \(i-1\) 递推而来，这提供了使用循环数组的可能。
不过用循环数组就不能用记忆化搜索了，要改成递推形式。
inline void GetInv(int len)
{inv[1]=1;for(int i=2;i<=len;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}signed main()
{GetInv(n+m);for(int i=1;i<=m;i++) f[0][i]=0;f[0][0]=f[1][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i%2][j]=i*inv[i+j]%mod;if(j>=2){int tmp=( j*inv[i+j]%mod )*( (j-1)*inv[i+j-1]%mod )%mod;if(j>=3) f[i%2][j]=( f[i%2][j]+tmp*f[i%2][j-3]%mod*( (j-2)*inv[i+j-2]%mod )%mod )%mod;if(i>=1) f[i%2][j]=( f[i%2][j]+tmp*f[(i-1)%2][j-2]%mod*( i*inv[i+j-2]%mod )%mod )%mod;}}for(int i=1;i<=m;i++) g[0][i]=0;g[0][0]=g[1][0]=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){g[i%2][j]=( j*inv[i+j]%mod )*( i*inv[i+j-1]%mod )%mod;if(j>=2){int tmp=( j*inv[i+j]%mod )*( (j-1)*inv[i+j-1]%mod )%mod;if(j>=3) g[i%2][j]=( g[i%2][j]+tmp*g[i%2][j-3]%mod*( (j-2)*inv[i+j-2]%mod )%mod )%mod;if(i>=1) g[i%2][j]=( g[i%2][j]+tmp*g[(i-1)%2][j-2]%mod*( i*inv[i+j-2]%mod )%mod )%mod;}}
}还是很好该的。
但是很遗憾，这样虽然解决的空间问题，但是时间复杂度依然很大，这个程序只有 \(60\text{pts}\)。
（目前笔者想不出优化的方法，先在此结文，等待教练讲解）