京セラプログラミングコンテスト2022（AtCoder Beginner Contest 271）G問題メモ

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271）

京セラと言えば、高耐久スマホのTORQUEは一時期お世話になってた。

G - Access Counter

• Webサイトにアクセスカウンターを設置する
• このサイトを訪れる可能性があるのは高橋くん、青木くんの2人しかいない
  • 毎時ちょうど（$i=0,1,2,...,23$ として $i$ 時00分）、どちらか片方のみにアクセスされる可能性がある
  • 長さ24の文字列 $c_0c_1c_2...c_{23}$ が与えられる
  • $c_i=$ 'T' なら $i$ 時に高橋くんが $X$ %の確率で1回訪れる
  • $c_i=$ 'A' なら $i$ 時に青木くんが $Y$ %の確率で1回訪れる
  • このことは、毎日、ずっと変わらず繰り返される
• 0時直前にアクセスカウンターをカウント“0”で設置した
• $N$ 回目に訪れるのが青木くんである確率を、有理数 $\mod{998244353}$ で求めよ
• $1 \le N \le 10^{18}$
• $1 \le X,Y \le 99$

経路数を隣接行列で求める手法を使えそう。

• 隣接行列で経路数を求める方法 「わかりやすく解説」 | ユーホス.com

隣接行列 $A$（頂点 $u→v$ に行く経路は $a_{u,v}$ 通りある、という値を全頂点間について表したもの）を用意すれば、 $N$ 回の移動で $u$ から出発して $v$ にいる経路数は、全頂点間まとめて $A^N$ で求められるよ、というもの。

これは、たとえば3回の移動で $u→○→△→v$ と移動したとして、

• $d_{u,○} \times d_{○,△} \times d_{△,v}$

を全てのあり得る○,△について足し合わせたものなので、 今回は $a_{u,v}$ に「前回のアクセスが $u$ 時で、次のアクセスが $v$ 時になる確率」を入れてやれば、 $A^N$ が「前回のアクセスが $u$ 時で、$N$ 回後のアクセスが $v$ 時になる、全 $(u,v)$ 間の確率」になる。

すると、$A^N[23][i]$ のうち、$c_i$ が青木くんの'A'である $i$ の確率を合計したものが答えとなる。

ダブリングを活用すれば $A^N$ は、$A$ の次数を $M$ として $O(M^3 \log{N})$ で求められるので、今回の制約にも間に合う。

「前回のアクセスが $u$ 時で、次のアクセスが $v$ 時になる確率」を各 $(u,v)$ について求めたい。

とはいえ、何日も全くアクセスが発生せず、無限に続くことがある。
それでいて、ちゃんと有理数の形で確率が算出できるのか？

であれば、無限和が収束するような式で表せて、何らかの式変形ができる？ という予測が立てられる。

（他に無限の確率を求める手法としては、 何らかの値を $x$ とおいて変数含みで2通りの方法で同じ値を示す式を求め、方程式を解く、というものもあるが、 この問題の場合は何かを $x$ とおいたとして、他の確率をそれで上手く表せそうもない）

ともかく、$u$ 時から見て次に訪れる $v$ 時でアクセスが発生したなら、

u              v
T  T  T  A  T  A

その確率は、例えば上記の並びなら以下のようになる。
ただし $\frac{X}{100},\frac{Y}{100}$ をそれぞれ $x,y$ とする。

• $(1-x)(1-x)(1-y)(1-x)y$

1周スルーしたなら、ちょうど1周アクセスが発生しない確率は $u,v$ に関わらず常に同じなので、これを $p$ とすると、

• $p \times (1-x)(1-x)(1-y)(1-x)y$

2周なら

• $p^2 \times (1-x)(1-x)(1-y)(1-x)y$

よって、これらを合計したものは

• $(1+p+p^2+p^3+...) \times (1-x)(1-x)(1-y)(1-x)y$

等比数列の無限和となる。これは $-1 \lt 公比 \lt 1$ の範囲で $\dfrac{初項}{1-公比}$ で表せるという公式があるので、

• $\dfrac{1}{1-p} \times (1-x)(1-x)(1-y)(1-x)y$

で、$a_{u,v}$ を計算できる。

解いている際は見落としていたが、 実際には $-1 \lt p \lt 1$ の範囲であっても、有理数modで表現すると $p \equiv 1$ となってしまい、 ゼロ除算が発生して計算ができなくなってしまう可能性がある。（例: $p=\dfrac{1755647}{10^9}$）

解説によると、$X,Y$ を99通り、$c_i$ に'A'が何個含まれるかで25通りが $p$ の取り得る全てなので、 全探索してそうならないことを確認してから使う、というのがあった。（マジか……）

まぁ、今回は全探索できるということだったが、そういう保証もない場合は、方針転換を考える必要がある。

（もっとも有理数modでの出力が求められる場合は、出題者によってちゃんとそう表せると証明されていることが普通で、 じゃあ「途中で分母が0になる分数が出てくるけど最終的には絶対に出てこない」ような問題ってどんなんだ、という気はする。 ので途中でそういうのが出てきたら方針自体違ってると考えられる……けど、 そう思っていたら逆に今回の問題も全探索すればいいことに気がつかないとハマる可能性があるわけで……難しい）

Python3

import numpy as np


def matrix_mul(mat1, mat2, MOD):
    mask = (1 << 15) - 1
    mat1h = mat1 >> 15
    mat1l = mat1 & mask
    mat2h = mat2 >> 15
    mat2l = mat2 & mask
    mathh = mat1h @ mat2h % MOD
    matll = mat1l @ mat2l % MOD
    mathl = (mathh + matll - (mat1h - mat1l) @ (mat2h - mat2l)) % MOD
    res = (mathh << 30) + (mathl << 15) + matll
    res %= MOD
    return res


n, x, y = map(int, input().split())
ccc = input()
MOD = 998244353

INV100 = pow(100, MOD - 2, MOD)
tak_x = (100 - x) * INV100 % MOD
aok_x = (100 - y) * INV100 % MOD

loop = 1
no_access = []
for c in ccc:
    if c == 'T':
        loop *= tak_x
        no_access.append(tak_x)
    else:
        loop *= aok_x
        no_access.append(aok_x)
    loop %= MOD

inf_loop = pow((1 - loop) % MOD, MOD - 2, MOD)

no_access = no_access + no_access
mat = [[0] * 24 for _ in range(24)]
for i in range(24):
    for j in range(24):
        if i >= j:
            j += 24
        res = 1
        for k in range(i + 1, j):
            res *= no_access[k]
            res %= MOD
        res *= (1 - no_access[j])
        mat[i][j % 24] = inf_loop * res % MOD

mat = np.array(mat, dtype=np.int64)
arr = np.eye(24, dtype=np.int64)
m = n
while m:
    if m & 1:
        arr = matrix_mul(arr, mat, MOD)
    mat = matrix_mul(mat, mat, MOD)
    m >>= 1

ans = 0
for i, c in enumerate(ccc):
    if c == 'A':
        ans += arr[-1, i]
        ans %= MOD

print(ans)