問題一覧 > 通常問題

No.3515 Anti EIKO

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : GaLLium / テスター : Yoyoyo8128 aa36 imabc yu23578 Germanium32 yt142857
ProblemId : 13127 / yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1 (順位表) / 自分の提出
問題文最終更新日: 2026-04-24 21:45:57
yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1の他の問題:

問題文

はじめ聖くんは長さ $4N$ の文字列 $T=$ SSSSS...SSSSSを持っており，気を失うまで以下の操作を繰り返します．

  • $T$ の先頭から $1$ 文字削除し，S,E,I,K,O の $5$ 種類の文字からランダムに $1$ 文字を選んで $T$ の末尾に追加する． ただし，どの文字も選ばれる確率は常に $\dfrac{1}{5}$ である． $T$ が文字列 EIKO を $N$ 個つなげた文字列となったとき，聖くんは気を失う．
聖くんが気を失うまでの操作回数がちょうど $K$ 回であるような確率を $\bmod 998244353$ で求めてください．

確率 $\bmod 998244353$ について

この問題の制約下で求める確率は必ず有理数 $Q$ になり，ある整数の組 $(X,Y) (X \not\equiv 0 \pmod{998244353})$ が存在して $XQ=Y$ を満たします． このとき $0 \leq Z \lt 998244353$ かつ $XZ \equiv Y \pmod{998244353}$ なる整数 $Z$ が一意に存在するので，その値を出力してください．

制約

  • 入力はすべて整数
  • $1 \leq N \leq 25$
  • $1 \leq K \leq 10^{18}$

入力

$N\ K$

出力

答えを $1$ 行で出力してください．

サンプル

サンプル1
入力
1 4
出力
771443236

$1,2,3,4$ 回目にそれぞれ E,I,K,O を選んだ場合のみ条件を満たします．確率は $\dfrac{1}{625}$ です． $\bmod 998244353$ で出力することに注意してください．

サンプル2
入力
2 7
出力
0

確率が $0$ になることもあります．$7$ 回の操作では覚えている文字列が EIKOEIKO になることはありません．

サンプル3
入力
19 123456789
出力
646671269

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。