AT_abc292_g [ABC292G] Count Strictly Increasing Sequences

题目描述

给定由数字（0123456789）和 ? 组成的长度为 $M$ 的字符串序列 $S_1,\ldots,S_N$。

将每个 ? 独立地替换为数字的方法共有 $10^q$ 种（$q$ 是 $S_1,\ldots,S_N$ 中所有 ? 的总数），在这些方法中，有多少种替换方式使得将替换后的每个字符串分别视为整数时，满足 $S_1 < S_2 < \ldots < S_N$？请输出满足条件的替换方式数对 $998244353$ 取模的结果。

注意，替换后的 $S_i$ 即使开头有一个或多个连续的 0 也没有关系。例如，将 0000000292 视为整数时为 $292$。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$S_1$
$\vdots$
$S_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2
?0
??
05

输出 #1

4

输入输出样例 #2

输入 #2

2 1
0
0

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $2 \leq N \leq 40$
• $1 \leq M \leq 40$
• $N, M$ 为整数
• $S_i$ 是由数字和 ? 组成的长度为 $M$ 的字符串

样例解释 1

满足条件的替换方式如下共 $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。

样例解释 3

请输出答案对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译