← 返回题目列表

Codeforces · 1065/E

E. 侧面转变

中文机器翻译题面 查看原题

考虑一组不同的字符 $$$A$$$ 和一些字符串 $$$S$$$,由 $$$n$$$ 字符组成,其中每个字符都出现在 $$$A$$$ 中。

给定一个 $$$m$$$ 整数数组 $$$b$$$ ($$$b_1 < b_2 < \dots < b_m$$$)。

您可以对字符串 $$$S$$$ 执行以下移动:

1. 选择一些有效的 $$$i$$$ 并设置 $$$k = b_i$$$;
2. 取$$$S的前$$$k$$$个字符 = Pr_k$$$;
3. 取$$$S的最后$$$k$$$个字符 = Su_k$$$;
4. 将 $$$S$$$ 的前 $$$k$$$ 字符替换为反转的 $$$Su_k$$$;
5. 将 $$$S$$$ 的最后 $$$k$$$ 字符替换为反转的 $$$Pr_k$$$。

例如,让我们看一下 $$$S =$$$ "abcdefghi" 和 $$$k = 2$$$。 $$$Pr_2 =$$$“ab”,$$$Su_2 =$$$“嗨”。反转$$$Pr_2 =$$$“ba”,$$$Su_2 =$$$“ih”。因此,生成的 $$$S$$$ 是“ihcdefgba”。

移动可以执行任意次数(可能为零)。任何 $$$i$$$ 都可以在这些移动中多次选择。

当且仅当存在将字符串 $$$S$$$ 转换为字符串 $$$T$$$ 的移动序列时,我们称某些字符串 $$$S$$$ 和 $$$T$$$ 相等。对于上面的示例,字符串“abcdefghi”和“ihcdefgba”是相等的。另请注意,这意味着 $$$S = S$$$。

任务很简单。计算不同字符串的数量。

答案可能足够大,因此请以 $$$998244353$$$ 为模进行计算。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$|A|$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le m \le min(\frac n 2, 2 \cdot 10^5)$$$, $$$1 \le |A| \le 10^9$$$) — 长度分别是字符串的大小、数组 $$$b$$$ 的大小和集合 $$$A$$$ 的大小。

第二行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le \frac n 2$$$, $$$b_1 < b_2 < \dots < b_m$$$)。

输出

打印单个整数 — 长度为 $$$n$$$ 且来自集合 $$$A$$$ 的字符以 $$$998244353$$$ 为模的不同字符串的数量。

示例

输入 #1

3 1 2
1

输出 #1

6

输入 #2

9 2 26
2 3

输出 #2

150352234

输入 #3

12 3 1
2 5 6

输出 #3

1

注意

这是第一个示例的所有不同字符串。所选择的字母“a”和“b”只是为了表明 $$$A$$$ 中的字符是不同的。

1.“aaa”
2.“aab”=“咩”
3.“阿巴”
4.“abb”=“bba”
5.“bab”
6.“bbb”