AT_abc292_g.[ABC292G] Count Strictly Increasing Sequences

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定由数字（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
```
3 2
?0
??
05
```
输出#1
```
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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页