

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
数字( 0123456789
)と ?
からなる長さ M の文字列の列 S_1,\ldots,S_N が与えられます。
?
を独立に数字に置き換える方法は 10^q(q は S_1,\ldots,S_N に含まれる ?
の個数の合計) 通りありますが、そのうち置き換え後の文字列をそれぞれ整数値とみなしたときに S_1\lt S_2 \lt \ldots \lt S_N が成り立つようなものが何通りあるかを 998244353 で割った余りを求めてください。
なお、?
を置き換えた後の S_i は先頭に 1 個以上の 0
が連続していても構いません。例えば、0000000292
を整数値とみなすと 292 となります。
制約
- 2 \leq N \leq 40
- 1 \leq M \leq 40
- N,M は整数
- S_i は数字と
?
からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 2 ?0 ?? 05
出力例 1
4
条件を満たす置き換え方は以下の 4 通りです。
- S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,1
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,2
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,3
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,4
に置き換える。
入力例 2
2 1 0 0
出力例 2
0
入力例 3
10 10 1?22??37?4 1??8?0??49 3?02??8044 51?4?8?7?? 5?9?20???2 68?7?6?800 ?3??2???23 ?442312158 ??2??921?8 ????5?96??
出力例 3
137811792
答えを 998244353 で割った余りを求めてください。
Score : 600 points
Problem Statement
You are given a sequence S_1,\ldots,S_N of length-M strings consisting of digits (0123456789
) and ?
.
There are 10^q ways to replace the occurrences of ?
with digits independently, where q is the total number of ?
in S_1,\ldots,S_N. Among them, how many satisfy S_1\lt S_2 \lt \ldots \lt S_N when the resulting strings are seen as integers? Find this count modulo 998244353.
The resulting strings may have leading zeros. For instance, 0000000292
is seen as 292.
Constraints
- 2 \leq N \leq 40
- 1 \leq M \leq 40
- N and M are integers.
- S_i is a string of length M consisting of digits and
?
.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
Print the answer.
Sample Input 1
3 2 ?0 ?? 05
Sample Output 1
4
Here are the four desired replacements.
- Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and1
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and2
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and3
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and4
, respectively.
Sample Input 2
2 1 0 0
Sample Output 2
0
Sample Input 3
10 10 1?22??37?4 1??8?0??49 3?02??8044 51?4?8?7?? 5?9?20???2 68?7?6?800 ?3??2???23 ?442312158 ??2??921?8 ????5?96??
Sample Output 3
137811792
Find the count modulo 998244353.