Problem:

Problem I: Coin and Die

Problem

  表と裏のあるコインと $1$ から $N$ までの目があるサイコロがある。Gachoくんはこれらを用いて以下のゲームをして遊ぶことにした。

  ゲームは最初に得点が $0$ の状態から始まり、以下の手順で進められる。

  

  
サイコロを $1$ 回振り、そのとき出た目の数を得点に加算する

  
現在の得点が $K$ 以上ならゲームクリアとなりゲームを終了する

  
現在の得点が $K$ 未満ならコインを投げ表が出れば1.に戻り、裏が出ればゲームオーバーとなりゲームを終了する

  

  コインは投げると $A\%$の確率で表になり、 $(100-A)\%$の確率で裏になる。また、サイコロは振ると、それぞれの目が等確率で出現する。

  このとき、一度のゲームでGachoくんがゲームクリアすることができる確率を求めよ。

  求める確率を互いに素な整数  $P, Q$ を用いて $\frac{P}{Q}$ と表したとき、 $R \times Q \equiv P\bmod 998244353$ となる $0$ 以上 $998244352$ 以下の整数 $R$ を出力せよ。この問題の制約下で、このような $R$ は必ず一意に存在する。

Input

入力は以下の形式で与えられる。

$N$ $K$ $A$

$N, K, A$ が空白区切りで一行に与えられる。

Constraints

入力は以下の条件を満たす。

  
$1 \leq N \leq 10^5 $

  
$1 \leq K \leq 10^5 $

  
$1 \leq A \leq 99 $

  
入力はすべて整数

Output

ゲームをクリアすることができる確率を互いに素な整数 $P, Q$を用いて $\frac{P}{Q}$ と表したとき、$R \times Q\equiv P\bmod 998244353$ となる $0$ 以上 $998244352$ 以下の整数 $R$ を出力せよ。

Sample Input 1

1 1 50

Sample Output 1

1

Sample Input 2

2 2 10

Sample Output 2

648858830

Sample Input 3

6 10 99

Sample Output 3

650893870



Sample input:
1 1 50


Sample output:
1

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353


def solve():
    n,k,a = LI()
    lst = [0]*(k+1)
    lst[-2] = 1
    A = a*pow(100*n,mod-2,mod)
    inv = pow(n,mod-2,mod)

    for i in range(k-1)[::-1]:
        if k > i + n:
            lst[i] = A*(lst[i+1] - lst[i+n+1]) + lst[i+1]
            lst[i] %= mod
        else:
            lst[i] = A*(lst[i+1] - lst[k]) + (n-(k-i)+1)*inv + lst[i+1]
            lst[i] %= mod
    print((lst[0] - lst[1])%mod)
    return


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, K, A = map(int, input().split())
dp = [0] * (K+1) + [1] * N  # 残りが i 点のときの勝率
dp[0] = 1
c = 1
mod = 998244353
p_coin = A * pow(100, mod-2, mod) % mod
p_dice = pow(N, mod-2, mod)
for i in range(1, K+1):
    dp[i] = c * p_coin % mod
    c += (dp[i] - dp[i-N]) * p_dice % mod
print(dp[K] * pow(p_coin, mod-2, mod) % mod)