問題一覧 > 通常問題

No.2964 Obstruction Bingo

レベル : / 実行時間制限 : 1ケース 2.468秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : ねしん / テスター : 遭難者
0 ProblemId : 11542 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-16 14:50:08

ストーリー

抽選箱から自分の望む数字が一切出てこなくて落ち込んで帰った懐かしい記憶。

物欲センサーでも働いているのですかね？

あたりはすんなり引ける方が良いに決まっています。

問題文

ナナとミンサはそれぞれ長さ LL の英小文字列 S=S0S1⋯SL−1S=S_0S_1 \cdots S_{L-1} 、T=T0T1⋯TL−1T=T_0T_1 \cdots T_{L-1} を持っています。

また、抽選箱には抽選カードが入っており、前から ii 番目の英小文字 (1≤i≤26)(1 \leq i \leq 26) は aia_i 枚入っています。抽選カードが選ばれる確率は等確率で試行ごとに戻す、つまり、前から ii 番目の英小文字 (1≤i≤26)(1 \leq i \leq 26) が選ばれる確率は、ai∑j=126aj\frac{a_i}{\sum_{j=1}^{26}a_j} です。

始め、両者の得点は 00 、つまり、ナナの得点を PNP_N、ミンサの得点を PMP_M としたとき、PN=PM=0P_N=P_M=0 です。勝敗が決まるか、KK 回行うまで次の行動を繰り返します。

  • 抽選箱からカードを取り出す。その文字を cc とする。c=SPN mod Lc=S_{P_N \ \text{mod}\ L} のとき、ナナは PNP_N に 11 を足し、c=TPM mod Lc=T_{P_M\ \text{mod} \ L} のとき、ミンサは PMP_M に 11 を足す。このとき、∣PN−PM∣=L|P_N-P_M|=L となったら、得点が大きいほうが勝者となる。


    • 勝敗が決まらなければ引き分けです。ナナとミンサの勝率をそれぞれ mod\text{mod} 998244353998244353 で求めてください。

    つまりそれぞれにおいて、確率は分母が 998244353998244353 と互いに素な既約分数表示を持つ有理数になるので、答えが既約分数で PQ\frac{P}{Q} となるとき Qx≡PQx \equiv P (mod(\text{mod} 998244353)998244353) となる整数 x(0≤x≤998244352)x(0 \leq x \leq 998244352) を求めてください。

    入力

    LL KK
SS
TT
a1a_1 a2a_2 ⋯\cdots a26a_{26}

  • 1≤L≤501 \leq L \leq 50
  • S,TS,T は長さ LL の英小文字列
  • 1≤K≤5001 \leq K \leq 500
  • 0≤ai≤107(1≤i≤26)0 \leq a_i \leq 10^7(1 \leq i \leq 26)
  • (a1,a2,⋯ ,a26)≠(0,0,⋯ ,0)(a_1,a_2,\cdots,a_{26}) \neq (0,0,\cdots,0)
  • L,K,ai(1≤i≤26)L,K,a_i(1 \leq i \leq 26) は整数

    • 出力

    ナナの勝つ確率を XX、ミンサの勝つ確率を YY としたとき、以下の様に出力してください。 

    XX YY

    サンプル

    サンプル1
    入力
    2 2
ab
cd
2 3 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    出力
    148499160 197998880

    ナナの勝率は 6121\frac{6}{121}、ミンサの勝率は 8121\frac{8}{121} となります。

    サンプル2
    入力
    4 10
abcd
bcde
0 2 5 2 5 2 5 2 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    出力
    0 798178412
    a が出ないのでナナは指をくわえて相手が上がるかどうかを見ていることしかできません。

    サンプル3
    入力
    5 100
ahjnp
ahjnp
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
    出力
    0 0

    得点の差がつかないので勝敗が決まることはありません。

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