問題一覧 > 通常問題

No.2964 Obstruction Bingo

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.468秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 39
作問者 : twitteryou / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 11542 / 自分の提出
問題文最終更新日: 2024-11-16 14:50:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 453 (順位表) の他の問題:

Story

A nostalgic memory: going home dejected because the numbers I wanted never came out of the lottery box at all.

Is some kind of "greed sensor" at work, I wonder?

It goes without saying that it is better when winning draws come easily.

Problem Statement

Nana and Minsa have strings of lowercase English letters $S=S_0S_1 \cdots S_{L-1}$ and $T=T_0T_1 \cdots T_{L-1}$, respectively, each of length $L$.

There is also a lottery box containing lottery cards: it contains $a_i$ cards of the $i$-th lowercase English letter from the front $(1 \leq i \leq 26)$. Each lottery card is chosen with equal probability and is returned after each trial; that is, the probability that the $i$-th lowercase English letter from the front $(1 \leq i \leq 26)$ is chosen is $\frac{a_i}{\sum_{j=1}^{26}a_j}$.

Initially, both players' scores are $0$; that is, letting $P_N$ be Nana's score and $P_M$ be Minsa's score, $P_N=P_M=0$. The following action is repeated until the outcome is decided or it has been performed $K$ times.

  • Draw a card from the lottery box. Let $c$ be its letter. If $c=S_{P_N \ \text{mod}\ L}$, Nana adds $1$ to $P_N$, and if $c=T_{P_M\ \text{mod} \ L}$, Minsa adds $1$ to $P_M$. If $|P_N-P_M|=L$ holds at this point, the player with the higher score becomes the winner.


    • If the outcome is not decided, the game is a draw. Find the winning probabilities of Nana and Minsa, each in $\text{mod}$ $998244353$.

    That is, each of these probabilities is a rational number whose irreducible fraction representation has a denominator coprime to $998244353$, so when the answer is $\frac{P}{Q}$ as an irreducible fraction, find the integer $x(0 \leq x \leq 998244352)$ such that $Qx \equiv P$ $(\text{mod}$ $998244353)$.

    Input

    $L$ $K$
$S$
$T$
$a_1$ $a_2$ $\cdots$ $a_{26}$

  • $1 \leq L \leq 50$
  • $S,T$ are strings of lowercase English letters of length $L$
  • $1 \leq K \leq 500$
  • $0 \leq a_i \leq 10^7(1 \leq i \leq 26)$
  • $(a_1,a_2,\cdots,a_{26}) \neq (0,0,\cdots,0)$
  • $L,K,a_i(1 \leq i \leq 26)$ are integers

    • Output

    Letting $X$ be the probability that Nana wins and $Y$ be the probability that Minsa wins, output them as follows. 

    $X$ $Y$

    Sample

    Sample 1
    Input
    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
    Output
    148499160 197998880

    Nana's winning probability is $\frac{6}{121}$, and Minsa's winning probability is $\frac{8}{121}$.

    Sample 2
    Input
    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
    Output
    0 798178412
    Since a never comes up, Nana can only stand by helplessly and watch whether her opponent finishes.

    Sample 3
    Input
    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
    Output
    0 0

    No difference in scores ever arises, so the outcome is never decided.

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