C - Calendar 2 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

Max Score: 500 Points

Problem Statement

We have a grid with n rows and 7 columns. We call it a calendar. The cell at i-th row and j-th column is denoted (i, j).
Initially, each cell at (i, j) contains the integer 7i + j - 8, and each cell is white.

Snuke likes painting, so he decided integer m, and did q operations with a calendar.
・In i-th operation, he paint black on the cell in which an integer is written such remainder of dividing by m is a_i.

Please count the number of connected white parts.
Note that if two adjacent cells are white, the cells belong to the same connected part.

Input Format

The input format is following:
n m q
a_1 a_2 ... a_q

Output Format

Print the number of connected part in one line.

Constraints

  • n ≤ 10^{12}
  • 7n is divisible by m.
  • 1 ≤ q ≤ m ≤ 10^5
  • 0 ≤ a_1 < a_2 < ... < a_q < m

Scoring

Subtask 1 [100 points]
  • n ≤ 100000.
Subtask 2 [90 points]
  • m is divisible by 7.
  • a_{i + 1} - a_i = 1.
Subtask 3 [200 points]
  • m is divisible by 7.
Subtask 4 [110 points]
  • There are no additional constraints.

Sample Input 1

7 7 3
1 3 5

Sample Output 1

4
The calendar looks like this:

Sample Input 2

10 14 8
5 6 7 8 9 10 11 12

Sample Output 2

10
The calendar looks like this:
配点：500 点

問題文

n × 7 のカレンダーがある。上から i 番目のマス、左から j 番目のマスを (i, j) で表す。
そのとき、マス (i, j) には整数 7i + j - 8 が書かれている。つまりカレンダーは次のようになっている。
すぬけ君は、塗り絵が大好きなので、このカレンダーを使って次のような遊びをした。
各マスは最初白く塗られており、すぬけ君は整数 m を決め、次のような操作を q 回行った。
  • i 回目の操作では、m で割った余りが a_i であるマスを黒く塗る。
すぬけ君は、白い部分は何個に分かれるか求めたかったので、白い連結な部分の個数を求めなさい。
ただし、白いマスに対して上下左右の4方向に白いマスがあれば、このマスは同じ連結な部分とみなすことにする。

入力

入力は、次の形式で与えられる。 
n m q
a_1 a_2 ... a_q

出力

連結な部分の個数を1行に出力しなさい。

制約

  • n ≦ 10^{12}
  • 7n は m で割り切れる。
  • 1 ≦ q ≦ m ≦ 10^5
  • 0 ≦ a_1 < a_2 < ... < a_q < m

得点

小課題1 [100 点]
  • n ≦ 100000.
小課題2 [90 点]
  • m は 7 の倍数
  • a_{i + 1} - a_i = 1.
小課題3 [200 点]
  • m は 7 の倍数
小課題4 [110 点]
  • 追加の制約はない。

入力例1

7 7 3
1 3 5

出力例1

4
次のようなカレンダーになる。よって、連結な部分の個数は 4 となる。

入力例2

10 14 8
5 6 7 8 9 10 11 12

出力例2

10
次のようなカレンダーになる。よって、連結な部分の個数は 14 10 (2020/8/08 訂正) となる。