問題一覧 > 通常問題

No.2291 Union Find Estimate

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 101
作問者 : t98slider / テスター : 👑 箱星
お気に入りにしたユーザー ProblemId : 9136 / 自分の提出
問題文最終更新日: 2023-11-18 08:07:42
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 387 (Union Find Contest) (順位表) の他の問題:

Problem Statement

Yukiko set a $W$-digit PIN consisting of the 10 kinds of digits from 0 to 9, but she has forgotten it.
So she made $H$ inquiries and obtained hints about the PIN.
Each reply to an inquiry is a string of $W$ characters, made up of the 37 kinds of characters 0 to 9, a to z, and ?.
Let $Q_{i}$ be the reply to the $i$-th ($1 \leq i \leq H $) inquiry, and let $Q_{i,j}$ be the $j$-th ($1 \leq j \leq W$) character of the reply to the $ i $-th inquiry.
Each $Q_{i, j}$ carries the following information.

  • If $Q_{i,j}$ is a digit from 0 to 9
    It means that the $j$-th digit from the left of the PIN is that digit.
  • If $Q_{i,j}$ is a letter from a to z
    It means that, for each $k$ such that $Q_{i,j} = Q_{i, k}$ in the reply to the $i$-th inquiry, the $j$-th digit from the left and the $k$-th digit from the left of the PIN are the same digit.
  • If $Q_{i,j}$ is ?
    It means that the reply to the $i$-th inquiry gives no information about the $j$-th digit from the left of the PIN.
On the $i$-th ($1 \leq i \leq H $) line, output the number of possible PINs at the point when the reply to the $i$-th inquiry has been received, modulo $\bmod\ 998244353$.
Note that for the $i$-th inquiry, the information from every $j$-th inquiry with $j < i$ is carried over.

Input

$W\ H$
$Q_{1}$
$Q_{2}$
$Q_{3}$
$\ \vdots$
$Q_{i}$
$\ \vdots$
$Q_{H}$

  • $1\leq W, H \leq 2 \times 10^{5} $
  • $1\leq W \times H \leq 2 \times 10^{5}$
  • $W, H$ are integers.
  • $|Q_{i}| = W$ holds for $1 \leq i \leq H$.
  • $Q_{i}$ is a string consisting of the 37 kinds of characters 0 to 9, a to z, and ?.

Output

On the $i$-th ($1 \leq i \leq H $) line, output the number of possible PINs at the point when the reply to the $i$-th inquiry has been received, modulo $\bmod\ 998244353$. Print a newline at the end.

Sample

Sample 1
Input
3 4
???
b1b
cc?
??2
Output
1000
10
1
0

  • The 1st inquiry gives no information. There are 1000 possible PINs, from 000 to 999, so output 1000.
  • The 2nd inquiry tells us that the 1st and 3rd digits from the left are equal, and that the 2nd digit from the left is 1.
    010, 111, 212, 313, 414, 515, 616, 717, 818, 919
    These 10 PINs are possible, so output 10.
  • The 3rd inquiry tells us that the 1st and 2nd digits from the left are equal. Combined with the 2nd inquiry, the PIN is determined uniquely as 111, so output 1.
  • The 4th inquiry tells us that the 3rd digit from the left is 2. Combined with the information so far, this contradicts the information that the 2nd digit is 1, so there are 0 possible PINs. Therefore, output 0.

Sample 2
Input
13 7
6qwfrtydfhjsf
6d?lghjknlmca
?df??1??????1
?q??fg?2????g
?3zxcvbnmasdf
6?aaa??2????1
?????z???zbed
Output
17556470
1755647
10000000
1000000
100000
1000
1000

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