分数: 700 点
问题陈述
给你整数 L, K 和一个长度-N 非负整数序列 A = (A_1, A_2, \ldots, A_N)。 在这里, 2K < L 和 0 \leq A_1 < A_2 < \cdots < A_N < L 得到保证。
考虑一个有周长的圆 L。 以该圆上任意一点为参考点,顺时针行驶距离所到达的点称为 x 从那里沿圆周沿坐标点 x。 另外,对于每个 i (1 \leq i \leq N),考虑连接点与坐标的弦 A_i 和坐标点 A_i + K,并调用这个和弦 i.
对于一组和弦 s, 分数 通过以下程序确定:
- 绘制其中包含的所有和弦 s。所画的弦将圆分成几个区域;将它们涂成白色和黑色。 首先,将包含圆心的区域着色为白色,并将其余区域着色为相邻区域(由正长度的线段连接)具有不同的颜色。 可以证明这样的着色方法总是唯一存在的。 分数是黑色区域的数量。
有 2^N 可能的设置 s。 求总和,取模 998244353,所有这些的分数。
约束
- 1 \leq K
- 2K < L \leq 10^9
- 1 \leq N \leq 250000
- 0 \leq A_1 < A_2 < \cdots < A_N < L
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
L K N A_1 A_2 \ldots A_N
输出
输出答案。
示例输入 1
5 2 2 0 1
示例输出 1
4
- 当未选择和弦时,分数为 0.
- 和弦时 选择 1 ,得分为 1.
- 和弦时 选择 2 ,得分为 1.
- 当和弦 选择 1, 2 ,得分为 2.
因此,答案是 4,这是这些的总和。
示例输入 2
3 1 1 2
示例输出 2
1
示例输入 3
5 2 5 0 1 2 3 4
示例输出 3
80
示例输入 4
7 3 3 0 2 3
示例输出 4
12