AT_arc198_e.[ARC198E] Monotone OR

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个由 $ 0 $ 到 $ 2^N - 1 $ 的非负整数组成的集合 $ S = { s_1, s_2, \dots, s_M } $。

你初始持有一个非负整数 $ x = 0 $。你可以进行以下操作任意次数，求使得 $ x = 2^N $ 的不同操作方法的数量，结果对 $ 998244353 $ 取模。

选择一个满足 $ 1 \le i \le M $ 的整数 $ i $，将 $ x $ 替换为 $ (x \ \mathrm{OR} \ s_i) + 1 $。

其中，$ \mathrm{OR} $ 表示按位或运算。

输入格式

输入通过标准输入给出，格式如下：

$ N $ $ M $
$ s_1 \ s_2 \ \dots \ s_M $

输出格式

输出使得 $ x = 2^N $ 的不同操作方法的数量，结果对 $ 998244353 $ 取模。

输入输出样例

输入#1
```
2 2
1 2
```
输出#1
```
5
```
输入#2
```
5 10
3 5 8 9 11 16 17 23 27 28
```
输出#2
```
242816764
```

输入#3

24 32
673802 709603 941436 987977 1288854 1448514 1890649 2031791 2194398 3531579 3540682 4352378 4676427 5094869 5243789 6064976 6412917 7164733 8403938 9123034 10396333 10558625 10726446 12263566 12421464 12503511 12676340 14032527 14268967 14669703 15823827 16285412

输出#3

508425421

说明/提示

约束条件

$ 1 \le N \le 24 $
$ 1 \le M \le \min(2^N, 2 \times 10^5) $
$ 0 \le s_1 < s_2 < \dots < s_M < 2^N $

样例解释 #1

如果用 $ (i, k) $ 表示选择 $ i $ 进行操作后 $ x $ 变为 $ k $，则满足条件的方法共有以下 $ 5 $ 种：

$ (1, 2) \rightarrow (1, 4) $
$ (1, 2) \rightarrow (2, 3) \rightarrow (1, 4) $
$ (1, 2) \rightarrow (2, 3) \rightarrow (2, 4) $
$ (2, 3) \rightarrow (1, 4) $
$ (2, 3) \rightarrow (2, 4) $

需要注意的是，即使 $ x $ 的转移路径完全相同，只要选择的 $ i $ 不同，就视为不同的方法。

翻译由 DeepSeek V3 完成

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

首页