← 返回题目列表

AtCoder · agc073_a

A. 和弦和方格

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

分数: 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