Count Strictly Increasing Sequences

题目描述

给定一个长度为 $M$ 的字符串序列 $S_1,\ldots,S_N$，这些字符串由数字（$0123456789$）和 $?$ 组成。 共有 $10^q$ 种方法独立地将 $S_1,\ldots,S_N$ 中出现的 $?$ 替换为数字，其中 $q$ 是 $S_1,\ldots,S_N$ 中 $?$ 的总数。在这些替换中，有多少种使得当替换后的字符串被视为整数时满足 $S_1\lt S_2 \lt \ldots \lt S_N$？对 $998244353$ 取模后输出该计数。 替换后的字符串可能有前导零。例如，$0000000292$ 被视为 $292$。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $S_1$ $\vdots$ $S_N$

输出格式

输出答案。

3 2
?0
??
05

4

2 1
0
0

0

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??

137811792

提示

$2 \leq N \leq 40$ $1 \leq M \leq 40$ $N$ 和 $M$ 是整数。 $S_i$ 是由数字和 $?$ 组成的长度为 $M$ 的字符串。下面是四种满足条件的替换。

将 $S_1$ 的第一个字符替换为 $0$，将 $S_2$ 的第一个和第二个字符分别替换为 $0$ 和 $1$。 将 $S_1$ 的第一个字符替换为 $0$，将 $S_2$ 的第一个和第二个字符分别替换为 $0$ 和 $2$。 将 $S_1$ 的第一个字符替换为 $0$，将 $S_2$ 的第一个和第二个字符分别替换为 $0$ 和 $3$。 将 $S_1$ 的第一个字符替换为 $0$，将 $S_2$ 的第一个和第二个字符分别替换为 $0$ 和 $4$。
对 $998244353$ 取模后输出计数。

标签: AtCoder|abc292G

来源

AtCoder|abc292G