打一局吗
题目描述
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}\)。
(目前笔者想不出优化的方法,先在此结文,等待教练讲解)