[acnoi2022] no way without guessing

tell the truth $\mathrm{c}\mathrm{n}\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{s}$ Just like a place to write a blog .$\mathrm{C}\mathrm{S}\mathrm{D}\mathrm{N}$ What is it

---

subject

Background
Follow $\text{OUYE}$ Learn together $\mathrm{O}\mathrm{I}$ It is a gamble in life . Poor thing is , No casino will let you win more and lose less .

Title Description
Do you have $x(0⩽x<1)$ money , You can gamble , The amount is any real number $y$, But you need $\{y_i\}$ Monotonous . if $x⩾1$ You win , It's impossible to achieve and lose .

Gambling rules ： cast $y$ money , Yes $p$ The probability is $2y$ money , Yes $(1-p)$ Probability is lost . Guarantee $p<\frac{1}{2}$ .

Find the probability of winning under the optimal strategy . Yes $998244353$ Take the mold output .

Data range and tips
$x=\frac{a_1}{b_1},p=\frac{a_2}{b_2}$, Yes $a_1<b_1⩽10^6$ And $2a_2<b_2⩽10^6$ .

Ideas

There are no examples , I will not get a cent . With the example , The score is still low . Get out of the math problem $\mathrm{O}\mathrm{I}$

Solve first $b_1=2^k$, That is to say $x$ Is a finite decimal under binary . It is impossible not to guess the conclusion .

Conclusion ： Every time $x$ The last one under binary $1$ Bet on the corresponding number .

prove ： First, relax the conditions , Don't ask for the amount of gambling not to drop . We will prove , In this looser decision tree , This is the optimal strategy .

The following is the proof of the solution . There are some places I can't quite understand , The place in doubt will be marked with .

Make $c(s)$ by $s$ Binary system $1$ The number of ,$f(x,n)(x\in \mathbb{N})$ by $\frac{x}{2^n}$ become $1$ Probability . Let's assume that the amount of gambling can only be $2^{-n}$ Multiple , So this is equivalent to $x\to 2^n$ Bet the whole amount each time . remember $q=1-p$ Then there is a recurrence
$$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)$$

because $2\nmid x$ I was gambling ,$2\mid x$ Time is shifting .

It's not hard to find out , This is actually a probability that $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ Carry or disappear . We enumerate where $\mathrm{b}\mathrm{i}\mathrm{t}$ On “ Let go ” 了 , Set to $i$ . about $\text{lcp}(x,i)$ Part of , If both are $1$, It means you missed it , It must be carried forward in one breath ; If both are $0$, Although I didn't miss , For final carry , The following must be carried . about $\text{lcp}$ The latter , if $x$ by $0$ and $i$ by $1$ Then there is no carry possibility , The opposite is always possible . So the back $\mathrm{b}\mathrm{i}\mathrm{t}$ It doesn't matter . It is not difficult to find that this is $i<x$ The judgment of the , thus
$$f(x,n)=\sum _{i=0}^{x-1}{q}^{c(i)}{p}^{n-c(i)}$$

The above text is a way of understanding ; Mathematical induction can also prove it .

Next, just prove $\forall k\in [0,x]\cap \mathbb{Z}$ Yes $f(x,n)⩾p\cdot f(x+k,n)+q\cdot f(x-k,n)$ . Press ： Something should be summed up here , Similar to the shortest circuit , Just verify that the distance label cannot be relaxed . But the shortest path can be as follows “ The number of shortest sides ” inductive , And you ？
$$\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}$$

We prove a super unequal relation ： There is bijection $f(t):[x,x+k)\mapsto [x-k,x)$ bring
$$q^{c(i)}{p}^{n-c(i)+1}⩽q^{c(f(i))+1}{p}^{n-c(f(i))}$$

That is, each item is smaller . I dare not put math problems in high school like this . It is equivalent to
$$q^{c(i)-c(f(i))-1}⩽p^{c(i)-c(f(i))-1}\Leftarrow c(i)-c(f(i))-1⩽0$$
because $q>p$ Well . The simplest way of thinking is , Make $f(i)$ by $i$ The result of removing a binary bit . Can it be done ？

set up $s=2^{\lceil {\log }_{2}k\rceil }$, Yes $i\in [x-k+s,x+k)$ Regulations $f(i)=i-s$ . There is one left $[x,x+s-k)\mapsto [x+k-s,x)$ Need to construct . Continuous recursion can complete the construction . Therefore, the conclusion is tenable .

$\square$

The other two are posted below “ prove ”, For reference only .

Proof of rain rabbit and sand duck

If you don't gamble $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$, Bet higher $\mathrm{b}\mathrm{i}\mathrm{t}$, After that $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ You can't bet , Rounding does not come up , It's useless. . If you bet lower $\mathrm{b}\mathrm{i}\mathrm{t}$, In the end, either $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ Carry or not carry , Better bet .

$\square$

The proof of Master Zhang

Basic strategy ： If the amount of money $⩽\frac{1}{2}$ Just $\text{all-in}$, Or bet $(1-x)$ . because $p<\frac{1}{2}$ So I expect that if I bet too much, I will only lose money , Better put all your eggs in one basket . We admit that it is optimal . Call it “ Basic strategy ”.

Then we prove that it is equivalent to another strategy ： remember $f(x)$ For the current $x$ Money is the bet of choice , be
$$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}$$

If you will $f(x)$ Draw the image of , So it was “ peak ” The shape of the , And this change is to make two “ hillside ” Change again to “ peak ”, Only a single point on the top of the mountain .

The proof process is vigorously developed . Here is to $\frac{1}{4}<x<\frac{1}{2}$ For example .
$$\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}$$

Note that the second line uses “ Basic strategy ” an ,$\text{all-in}$ Result . Press ： It feels like an obscure induction , namely “ Other locations used this strategy to fit the same winning rate , Therefore, it can be directly expanded by the winning rate equation of the original strategy ”. But it's hard to generalize .

Or say , I proved “ Adjust the first step strategy to get the same winning rate ”, And each step is equivalent to the first step , So every step can be adjusted ？ It's always strange to say .

The result of direct expansion is
$$g(x)=p\cdot g(2x)=p^2+pq\cdot g(4x-1)$$

So it works . Empathy , We can transform “ hillside ” Replace with “ peak ”.

It is not difficult to find out that in the end $f(\frac{s}{2^k})=\frac{1}{2^k}(2\nmid s)$ . This is every bet $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}$ Well .

$\square$

use $\mathtt{d}\mathtt{p}$ Rewrite the above procedure ：$f_{i,0/1}$ It's the second time at present $i$ position , Whether there is a carry winning probability after . The transition is linear .

If at present $\mathrm{b}\mathrm{i}\mathrm{t}$ by $0$, Then it is transferred to
$$f_i=\left(\begin{array}{cc}1& 0\\ q& p\end{array}\right)f_{i-1}$$

among $f_i=\left(\begin{array}{c}{f}_{i,0}\\ f_{i,1}\end{array}\right)$ . This transfer will not be discussed in detail , Just be patient .

If at present $\mathrm{b}\mathrm{i}\mathrm{t}$ by $1$, Then it is transferred to
$$f_i=\left(\begin{array}{cc}q& p\\ 0& 1\end{array}\right)f_{i-1}$$

about $b_i=2^n$ The situation of , We have $\mathcal{O}(n)$ It's solved . otherwise $x$ It's an infinite circular decimal .

obviously $x$ The length of the loop section of does not exceed $b$ . Let the matrix of a single cyclic node be $B$, The matrix of the non pure cyclic part is $A$ . Then we only need to solve
$$\underset{n\to +\infty }{\lim }{B}^{n}A\left(\begin{array}{c}0\\ 1\end{array}\right)$$

The general method is probably diagonalization . But in this question $B$ Is a very recurrent Markov matrix , The steady state can be solved directly . Notice the line vector ！

Code

#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;
}