Chords and Checkered

AtCoder

IDagc073_a

Time2000ms

Memory256MB

Difficulty—

You are given integers $L, K$ and a length-$N$ non-negative integer sequence $A = (A_1, A_2, \ldots, A_N)$. Here, $2K < L$ and $0 \leq A_1 < A_2 < \cdots < A_N < L$ are guaranteed. Consider a circle with circumference $L$. Take an arbitrary point on this circle as the reference point, and call the point reached by traveling clockwise distance $x$ along the circumference from there the point with coordinate $x$. Also, for each $i$ ($1 \leq i \leq N$), consider the chord connecting the point with coordinate $A_i$ and the point with coordinate $A_i + K$, and call this chord $i$. For a set of chords $s$, the **score** is determined by the following procedure: * Draw all chords contained in $s$. The drawn chords divide the circle into several regions; color them with white and black. First, color the region containing the center of the circle white, and color the remaining regions so that adjacent regions (connected by a line segment of positive length) have different colors. It can be proved that such a coloring method always exists uniquely. The score is the number of regions colored black. There are $2^N$ possible sets for $s$. Find the sum, modulo $998244353$, of scores for all of these. ## Constraints * $1 \leq K$ * $2K < L \leq 10^9$ * $1 \leq N \leq 250000$ * $0 \leq A_1 < A_2 < \cdots < A_N < L$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $L$ $K$ $N$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

5 2 2
0 1

Output #1

4

*   When no chords are chosen, the score is $0$.
*   When chord $1$ is chosen, the score is $1$.
*   When chord $2$ is chosen, the score is $1$.
*   When chords $1, 2$ are chosen, the score is $2$.

Therefore, the answer is $4$, which is the sum of these.

Input #2

3 1 1
2

Output #2

Input #3

5 2 5
0 1 2 3 4

Output #3

Input #4

7 3 3
0 2 3

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Chords and Checkered",
    "description": {
      "content": "You are given integers $L, K$ and a length-$N$ non-negative integer sequence $A = (A_1, A_2, \\ldots, A_N)$. Here, $2K < L$ and $0 \\leq A_1 < A_2 < \\cdots < A_N < L$ are guaranteed. Consider a circle w",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc073_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $L, K$ and a length-$N$ non-negative integer sequence $A = (A_1, A_2, \\ldots, A_N)$. Here, $2K < L$ and $0 \\leq A_1 < A_2 < \\cdots < A_N < L$ are guaranteed.\nConsider a circle w...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments