AtCoder Beginner Contest 292
翻译中…
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.
翻译中…
样例
Input #1
3 2
?0
??
05
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$ with `0` and `1`, respectively.
- Replace the first character of $S_1$ with `0`, and the first and second characters of $S_2$ with `0` and `2`, respectively.
- Replace the first character of $S_1$ with `0`, and the first and second characters of $S_2$ with `0` and `3`, respectively.
- Replace the first character of $S_1$ with `0`, and the first and second characters of $S_2$ with `0` and `4`, respectively.
Input #2
2 1
0
0
Output #2
0
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??
Output #3
137811792
Find the count modulo $998244353$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。