[ACNOI2022]不猜不行

说老实话 $\mathrm{c}\mathrm{n}\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{s}$ 才像个写博客的地方。$\mathrm{C}\mathrm{S}\mathrm{D}\mathrm{N}$ 是啥玩意儿啊

---

题目

题目背景
跟 $\text{OUYE}$ 一起学 $\mathrm{O}\mathrm{I}$ 是人生的豪赌。可怜的是，没有哪个赌场会让你赢多输少。

题目描述
你有 $x(0⩽x<1)$ 钱，你可以赌博，金额为任意实数 $y$，但需要 $\{y_i\}$ 单调不降。若 $x⩾1$ 你就赢，不可能实现了你就输。

赌博规则：投 $y$ 钱，有 $p$ 概率得 $2y$ 钱，有 $(1-p)$ 概率血本无归。保证 $p<\frac{1}{2}$ 。

求最优策略下赢的概率。对 $998244353$ 取模输出。

数据范围与提示
$x=\frac{a_1}{b_1},p=\frac{a_2}{b_2}$，有 $a_1<b_1⩽10^6$ 且 $2a_2<b_2⩽10^6$ 。

思路

没有样例，我将一分不得。有了样例，得分仍然寥寥。数学题滚出 $\mathrm{O}\mathrm{I}$

先解决 $b_1=2^k$，也就是 $x$ 是二进制下有限小数。不猜结论是不可能的。

结论：每次取 $x$ 二进制下最后一个 $1$ 对应的数去赌。

证明：首先将条件放宽，不要求赌的数额不降。我们将证明，在这更宽松的决策树中，这是最优策略。

下面是题解的证明。有些地方我不能很理解，存疑处将标出。

令 $c(s)$ 为 $s$ 的二进制 $1$ 的个数，$f(x,n)(x\in \mathbb{N})$ 为 $\frac{x}{2^n}$ 变成 $1$ 的概率。我们先假设赌的数额只能是 $2^{-n}$ 的倍数，因此这等价于 $x\to 2^n$ 每次赌整数金额。记 $q=1-p$ 则有递推式
$$f(x,n)=p\cdot f\left(\lceil \frac{x}{2}\rceil ,n-1\right)+q\cdot f\left(\lfloor \frac{x}{2}\rfloor ,n-1\right)$$

因为 $2\nmid x$ 时在赌，$2\mid x$ 时在转移。

不难发现，这其实是概率性地让 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ 进位或消失。我们枚举在哪些 $\mathrm{b}\mathrm{i}\mathrm{t}$ 上 “失手” 了，设为 $i$ 。对于 $\text{lcp}(x,i)$ 的部分，若均为 $1$，说明失手了，必须后面进位一口气飞跃；若均为 $0$，尽管没失手，为了最终进位，后面必须进位。对于 $\text{lcp}$ 后一位，若 $x$ 为 $0$ 而 $i$ 为 $1$ 则无进位可能，反之则总可行。那么后面的 $\mathrm{b}\mathrm{i}\mathrm{t}$ 的情况都不重要。不难发现这就是 $i<x$ 的判断，由此
$$f(x,n)=\sum _{i=0}^{x-1}{q}^{c(i)}{p}^{n-c(i)}$$

上面的文字是一种理解方式；数学归纳法也可以证明之。

接下来只需证明 $\forall k\in [0,x]\cap \mathbb{Z}$ 有 $f(x,n)⩾p\cdot f(x+k,n)+q\cdot f(x-k,n)$ 。按：此处应当对某物进行了归纳，类似最短路，只需验证距离标号不可被松弛。可是最短路可以按照“最短路边数”归纳，而你呢？
$$\begin{array}{rl}p(f(x+k,n)-f(x,n))& ⩽q(f(x,n)-f(x-k,n))\\ \iff \sum _{i=0}^{k-1}{q}^{c(i+x)}{p}^{n-c(i+x)+1}& ⩽\sum _{i=1}^k{q}^{c(x-i)+1}{p}^{n-c(x-i)}\end{array}$$

我们证明一个超强不等关系：存在双射 $f(t):[x,x+k)\mapsto [x-k,x)$ 使得
$$q^{c(i)}{p}^{n-c(i)+1}⩽q^{c(f(i))+1}{p}^{n-c(f(i))}$$

即每一项都对应更小。高中数学题都不敢这么放。它等价于
$$q^{c(i)-c(f(i))-1}⩽p^{c(i)-c(f(i))-1}\Leftarrow c(i)-c(f(i))-1⩽0$$
因为 $q>p$ 嘛。最简单的思路是，令 $f(i)$ 为 $i$ 去掉某个二进制位的结果。能否做到呢？

设 $s=2^{\lceil {\log }_{2}k\rceil }$，对 $i\in [x-k+s,x+k)$ 规定 $f(i)=i-s$ 。还剩下一个 $[x,x+s-k)\mapsto [x+k-s,x)$ 需构造。不断递归即可完成构造。故结论成立。

$\square$

下面贴出另外两种“证明”，仅供参考。

雨兔和沙鸭的证明

如果不赌 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$，赌更高 $\mathrm{b}\mathrm{i}\mathrm{t}$，那以后 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ 就赌不得，进位不上来，就没用了。如果赌更低 $\mathrm{b}\mathrm{i}\mathrm{t}$，反正最后要么 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ 进位要么不进位，不如赌。

$\square$

张教主的证明

基本策略：若钱数 $⩽\frac{1}{2}$ 就 $\text{all-in}$，否则赌 $(1-x)$ 。因为 $p<\frac{1}{2}$ 所以期望下赌多了只会输钱，不如孤注一掷。我们承认它是最优的。称其为“基本策略”。

然后我们证明它和另一策略等价：记 $f(x)$ 为当前 $x$ 钱时选择的赌注，则
$$f(x)=\{\begin{array}{ll}\frac{1}{2}& (x=\frac{1}{2})\\ \frac{1}{4}-|x-\frac{1}{4}|& (x<\frac{1}{2})\\ \frac{1}{4}-|x-\frac{3}{4}|& (x>\frac{1}{2})\end{array}$$

如果将 $f(x)$ 的图像画出来，那么原本是“山峰”的形状，而这一变化是将两个“山坡”再次换成“山峰”，只保留山巅的单点。

证明过程是大力展开。这里就以 $\frac{1}{4}<x<\frac{1}{2}$ 为例。
$$\begin{array}{rl}g(x)& =p\cdot g\left(\frac{1}{2}\right)+q\cdot g\left(2x-\frac{1}{2}\right)\\ & =p^2+qp\cdot g(4x-1)(0.25<x<0.5)\end{array}$$

注意第二行是用“基本策略”展开，$\text{all-in}$ 的结果。按：这里感觉像一个隐晦的归纳法，即“其他位置用这个策略拟合出了相同的胜率，因此可以直接用原策略的胜率方程展开”。但是这东西很难归纳。

或者说，我证明了“调整第一步策略可以得到相同胜率”，而每一步都相当于第一步，所以每一步都可以调整？说起来总是怪怪的。

而直接展开的结果是
$$g(x)=p\cdot g(2x)=p^2+pq\cdot g(4x-1)$$

所以可行。同理，我们可以无限地将“山坡”替换成“山峰”。

不难发现最终 $f(\frac{s}{2^k})=\frac{1}{2^k}(2\nmid s)$ 。这就是每次赌 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ 嘛。

$\square$

用 $\mathtt{d}\mathtt{p}$ 重写上面过程：$f_{i,0/1}$ 表示当前是第 $i$ 位，后是否有进位的赢概率。转移是线性变化。

若当前 $\mathrm{b}\mathrm{i}\mathrm{t}$ 为 $0$，则转移为
$$f_i=\left(\begin{array}{cc}1& 0\\ q& p\end{array}\right)f_{i-1}$$

其中 $f_i=\left(\begin{array}{c}{f}_{i,0}\\ f_{i,1}\end{array}\right)$ 。这个转移就不细说了，只需要足够的耐心。

若当前 $\mathrm{b}\mathrm{i}\mathrm{t}$ 为 $1$，则转移为
$$f_i=\left(\begin{array}{cc}q& p\\ 0& 1\end{array}\right)f_{i-1}$$

对于 $b_i=2^n$ 的情况，我们已经 $\mathcal{O}(n)$ 解决了。否则 $x$ 是无限循环小数。

显然 $x$ 的循环节长度不超过 $b$ 。设单个循环节的矩阵是 $B$，非纯循环部分的矩阵是 $A$ 。则只需求解
$$\underset{n\to +\infty }{\lim }{B}^{n}A\left(\begin{array}{c}0\\ 1\end{array}\right)$$

通用方法大概是对角化。但本题中 $B$ 是非常返马尔科夫矩阵，可以直接解出稳态。注意是行向量！

代码

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // Huge Egg Dog ate me!!!
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MOD = 1e9+7;
inline llong qkpow(llong b, int q){
    
	llong a = 1;
	for(; q; q>>=1,b=b*b%MOD) if(q&1) a = a*b%MOD;
	return a;
}

struct Matrix{
    
	int a00, a01, a10, a11;
	Matrix operator * (const Matrix &b) const {
    
		Matrix c;
		c.a00 = int((llong(a00)*b.a00+llong(a01)*b.a10)%MOD);
		c.a01 = int((llong(a00)*b.a01+llong(a01)*b.a11)%MOD);
		c.a10 = int((llong(a10)*b.a00+llong(a11)*b.a10)%MOD);
		c.a11 = int((llong(a10)*b.a01+llong(a11)*b.a11)%MOD);
		return c;
	}
	static Matrix I(){
    
		Matrix c; c.a00 = c.a11 = 1;
		c.a01 = c.a10 = 0; return c;
	}
	Matrix bite(){
    
		Matrix c;
		if(a00 != 1){
    
			// (a00-1)*x+a10*y = 0
			// x+y = 1 => (a00-1-a10)*x+a10 = 0
			c.a00 = c.a10 = int(qkpow(1+a10+MOD-a00,MOD-2)*a10%MOD);
			c.a01 = c.a11 = 1+MOD-c.a00; // Markov
		}
		else{
    
			// a01*x+(a11-1)*y = 0
			// x+y = 1 => (a11-1-a01)*y+a01 = 0
			c.a01 = c.a11 = int(qkpow(1+a01+MOD-a11,MOD-2)*a01%MOD);
			c.a00 = c.a10 = 1+MOD-c.a11;
		}
		return c;
	}
};
Matrix mat[2];

const int MAXB = 1000000;
int pos[MAXB]; bool bit[MAXB];
int main(){
    
	for(int T=readint(),a,b,p; T; --T){
    
		a = readint(), b = readint(), p = readint();
		p = int(qkpow(readint(),MOD-2)*p%MOD);
		mat[0].a00 = 1, mat[0].a01 = 0;
		mat[0].a10 = 1+MOD-p, mat[0].a11 = p;
		mat[1].a00 = 1+MOD-p, mat[1].a01 = p;
		mat[1].a10 = 0, mat[1].a11 = 1;
		memset(pos, -1, b<<2);
		int st = 0, ed = 0;
		for(int i=0; true; ++i){
    
			if(~pos[a]){
     // cycle found
				st = pos[a], ed = i; break;
			}
			pos[a] = i; // record
			if((a<<=1) >= b)
				a -= b, bit[i] = true;
			else bit[i] = false;
		}
		Matrix ddg = Matrix::I();
		rep0(i,st,ed) ddg = mat[bit[i]]*ddg;
		ddg = ddg.bite(); // infinite power
		drep(i,st-1,0) ddg = ddg*mat[bit[i]];
		printf("%d\n",ddg.a01);
	}
	return 0;
}