E - BDFS
Source: atcoder
Difficulty: 800

Problem Statement
You are given integers
N
and
P
.
There is a graph with
N
vertices and
N
edges, where each vertex is labeled
1
to
N
. The
i
-th edge connects vertices
i
and
i+1
bidirectionally. Here, vertex
N+1
refers to vertex
1
.
Perform the following algorithm to obtain a sequence
D=(D_1,D_2,\ldots,D_N)
of length
N
:
Set an integer sequence
D
of length
N
to
D=(D_1,\ldots,D_N)=(-1,\ldots,-1)
. Also, set a sequence
Q
of number pairs to
Q=((1,0))
. Repeat the following process while
Q
is not empty:
Let
(v,d)
be the first element of
Q
. Remove this element.
If
D_v = -1
, then set
D_v := d
, and for each vertex
x
adjacent to vertex
v
such that
D_x=-1
, perform the following process. If there are multiple such
x
that satisfy the condition, process them in ascending order of vertex number:
With probability
\frac{P}{100}
, add
(x,d+1)
to the
front
of
Q
.
If
(x,d+1)
was not added to the front of
Q
, add it to the
end
of
Q
.
Find the expected value of the sum of the elements of the final sequence
D
obtained, modulo
998244353
.
Solve each of the
T
test cases given.
Definition of expected value
\text{mod } 998244353
It can be proved that the expected value to be found is always a rational number.
Furthermore, the constraints of this problem guarantee that if that value is expressed as an irreducible fraction
\frac{P}{Q}
, then
Q
is not divisible by
998244353
.  
Here, there is a unique integer
R
between
0
and
998244352
, inclusive, such that
R\times Q \equiv P\pmod{998244353}
. Provide this
R
as the answer.
Constraints
1 \leq T \leq  10^4
3 \leq N \leq 10^{18}
1\leq P \leq 99
All input numbers are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N
P
Output
Print
T
lines. The
i
-th line
(1 \leq i \leq T)
should contain the answer for the
i
-th test case.
Sample Input 1
3
3 50
4 1
1000000000000000000 70
Sample Output 1
499122179
595552585
760296751
In the first test case, the algorithm may operate as follows:
Initially,
D=(-1,-1,-1)
and
Q=((1,0))
. Remove the first element
(1,0)
from
Q
.
D_1 = -1
, so set
D_1 := 0
. The vertices
x
adjacent to vertex
1
such that
D_x= -1
are
2
and
3
.
Add
(2,1)
to the front of
Q
. Add
(3,1)
to the end of
Q
. Now
Q=((2,1),(3,1))
.
Remove the first element
(2,1)
from
Q
.
D_2 = -1
, so set
D_2 := 1
. The vertex
x
adjacent to vertex
2
such that
D_x= -1
is
3
.
Add
(3,2)
to the front of
Q
. Now
Q=((3,2),(3,1))
.
Remove the first element
(3,2)
from
Q
.
D_3 = -1
, so set
D_3 := 2
. There are no vertices
x
adjacent to vertex
3
such that
D_x= -1
, so do nothing.
Remove the first element
(3,1)
from
Q
.
D_3 =2
, so do nothing.
Q
is now empty, so the process ends.
In this case, the final sequence obtained is
D=(0,1,2)
. The probability that the algorithm operates as described above is
\frac{1}{8}
, and the expected sum of the elements of
D
is
\frac{5}{2}
.

C++ solution:
#include<bits/stdc++.h>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define O(x) cout<<__LINE__<<""#x ":"<<(x)<<endl;
#define PII pair<int,int>
#define PDD pair<du,du>
#define fi first
#define se second
#define du double
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define SZ(t)((int)((t).size()))
#define eps (1e-14)
#define N 111111
#define LL long long
#define int LL
using namespace std;
const int mod=998244353;
int fast_pow(int a,int b){
	a%=mod;
	b%=mod-1;
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int C2(int a){
	a%=mod;
	return a*(a-1)%mod*(mod+1)/2%mod;
}
signed main(){
	int TTTT;
	scanf("%lld",&TTTT);
	while(TTTT--){
		int n,p;
		scanf("%lld%lld",&n,&p);
		p=p*fast_pow(100,mod-2)%mod;
		p=(2*p-1+mod)%mod;
		int pw=fast_pow(p,n-1);
		int inv=fast_pow(p-1,mod-2);
		int ss=(pw-1)*inv%mod;
		int ans=C2(n)+(ss-1-pw*(n%mod-2))%mod*inv+ss*(n%mod-1);
		ans=(ans%mod+mod)%mod*((mod+1)/2)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const MOD = 998244353

func powMod(a, b, mod int64) int64 {
	res := int64(1)
	a = a % mod
	for b > 0 {
		if b%2 == 1 {
			res = (res * a) % mod
		}
		a = (a * a) % mod
		b = b >> 1
	}
	return res
}

func invMod(x, mod int64) int64 {
	return powMod(x, mod-2, mod)
}

func solve() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < T; i++ {
		scanner.Scan()
		line := scanner.Text()
		parts := strings.Split(line, " ")
		N, _ := strconv.ParseInt(parts[0], 10, 64)
		P, _ := strconv.ParseInt(parts[1], 10, 64)
		P = P * 828542813 % MOD
		Q := (P - 1) % MOD
		if Q < 0 {
			Q += MOD
		}
		term1 := (N % MOD) * Q % MOD
		term1 = (term1 - P) % MOD
		if term1 < 0 {
			term1 += MOD
		}
		term2 := 2 * N % MOD
		term2 = term2 * Q % MOD
		term1 = term1 * term2 % MOD
		powTerm := powMod((P+Q)%MOD, N, MOD)
		term3 := (powTerm - 1) % MOD
		if term3 < 0 {
			term3 += MOD
		}
		numerator := (term1 + term3) % MOD
		denominator := 8 * Q % MOD
		denominator = denominator * Q % MOD
		invDenominator := invMod(denominator, MOD)
		ans := numerator * invDenominator % MOD
		fmt.Println(ans)
	}
}

func main() {
	solve()
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 998244353;
    static final long INV100 = 828542813; // Modular inverse of 100 under MOD

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long N = Long.parseLong(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
            
            long p = (long) P * INV100 % MOD;
            long q = (p - 1 + MOD) % MOD;
            
            long term1 = (N % MOD) * q % MOD;
            term1 = (term1 - p + MOD) % MOD;
            term1 = term1 * 2 % MOD;
            term1 = term1 * (N % MOD) % MOD;
            term1 = term1 * q % MOD;
            
            long pq = (p + q) % MOD;
            long powPQ = pow(pq, N);
            
            long numerator = (term1 + powPQ - 1 + MOD) % MOD;
            long denom = 8 * q % MOD;
            denom = denom * q % MOD;
            denom = pow(denom, MOD - 2);
            
            long res = numerator * denom % MOD;
            out.println(res);
        }
        out.close();
    }
    
    static long pow(long a, long b) {
        long res = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
}

JavaScript solution:
const readline = require('readline');

const MOD = 998244353n;

// Efficient modular exponentiation
function modPow(a, b, mod) {
    let result = 1n;
    a = a % mod;
    while (b > 0n) {
        if (b % 2n === 1n) {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b = b >> 1n;
    }
    return result;
}

// Modular inverse using Fermat's Little Theorem
function modInverse(a, mod) {
    return modPow(a, mod - 2n, mod);
}

function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    let input = [];
    rl.on('line', (line) => {
        input.push(line.trim());
    });

    rl.on('close', () => {
        const T = parseInt(input[0]);
        for (let i = 1; i <= T; i++) {
            const [N, P] = input[i].split(' ').map(BigInt);
            
            // Precompute constants
            const P_mod = (P * 828542813n) % MOD;
            const Q_mod = (P_mod - 1n + MOD) % MOD;
            const N_mod = N % MOD;
            
            // Calculate numerator components
            const term1 = (N_mod * Q_mod - P_mod + MOD) % MOD;
            const term2 = (2n * N_mod * Q_mod) % MOD;
            const pow_term = modPow((P_mod + Q_mod) % MOD, N, MOD);
            
            // Combine numerator terms
            const numerator = (term1 * term2 % MOD + pow_term - 1n + MOD) % MOD;
            
            // Calculate denominator inverse
            const denominator = (8n * Q_mod % MOD * Q_mod) % MOD;
            const denominator_inv = modInverse(denominator, MOD);
            
            // Final result
            const result = (numerator * denominator_inv) % MOD;
            console.log(result.toString());
        }
    });
}

main();

Python solution:
I=input
M=998244353
for _ in[0]*int(I()):N,P=map(int,I().split());P*=828542813;Q=P-1;print(((N*Q-P)*2*N*Q+pow(P+Q,N,M)-1)*pow(8*Q*Q,-1,M)%M)

Ruby solution:
require 'set'

MOD = 998244353

def solve
  input = $stdin.read.split
  idx = 0
  t = input[idx].to_i
  idx += 1
  t.times do
    n = input[idx].to_i
    p = input[idx + 1].to_i
    idx += 2
    
    # Convert P to a fraction in the modular field
    p = p * 828542813 % MOD
    q = (p - 1) % MOD
    
    # Compute term1: (N * Q - P) * 2 * N * Q
    term1 = (n * q - p) % MOD
    term1 = (term1 * 2) % MOD
    term1 = (term1 * n) % MOD
    term1 = (term1 * q) % MOD
    
    # Compute term2: (P + Q)^N - 1
    pq = (p + q) % MOD
    pow_pq_n = pq.pow(n, MOD)
    term2 = (pow_pq_n - 1) % MOD
    
    # Total terms
    total = (term1 + term2) % MOD
    
    # Compute the denominator's inverse: 1 / (8 * Q^2)
    denominator = (8 * q * q) % MOD
    inv_denominator = denominator.pow(MOD - 2, MOD)
    
    # Final result
    res = (total * inv_denominator) % MOD
    puts res
  end
end

solve