G - Caeser Syllables 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

0 から K-1 までの番号で表される K 種類の記号があります。

各記号は、母音であるか母音でないかのいずれかです。 V_j = 1 のとき記号 j は母音であり、V_j = 0 のとき記号 j は母音ではありません。

ある記号列の音節数を、その記号列における母音のみからなる連続部分列として極大なものの個数とします。形式的には、長さ N の記号列 (a_1, \dots, a_N) の音節数を、1 \leq l \leq r \leq N を満たす整数の組 (l,r) であって以下をすべて満たすものの個数とします。

  • 記号 a_l, \dots, a_r はすべて母音である。
  • l > 1 ならば、記号 a_{l-1} は母音でない。
  • r < N ならば、記号 a_{r+1} は母音でない。

長さ N の数列 A = (A_1, \dots, A_N) が与えられます。k = 0, \dots, K-1 について、以下の問題に答えてください。

  • 長さ N の記号列 A' = (A'_1, \dots, A'_N) を、A'_i := (A_i + k) \bmod K として定める。このとき、A' の音節数はいくつか?

入力の形式

今回の問題の入力は特殊な形式で行われます。

標準入力からは A_1, \dots, A_N の代わりに整数 \mathrm{seed}, M, b_1, \dots, b_M が与えられます。 このとき、以下の疑似コードで表される計算によって A_1, \dots, A_N を復元してください。

なお、疑似コード中の変数はすべて符号なし 64bit 整数であるものとします。 また、s \oplus t は s,t の bitwise XOR (排他的論理和) を、s \gg t は \lfloor s / 2^t \rfloor (右シフト演算) を、s \ll t は s \times 2^t (左シフト演算) を表すものとします。

\mathrm{state} \leftarrow \mathrm{seed}

for i = 1, \dots, N:
    if i \leq M:
        A_i \leftarrow b_i
    else:
        x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32}
        r \leftarrow \mathrm{state} \gg 59
        y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32}
        A_i \leftarrow y \bmod K
        \mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}

制約

  • 1 \leq N \leq 7 \times 10^6
  • 1 \leq K \leq 2300
  • 0 \leq A_i \leq K-1 (1 \leq i \leq N)
  • V_j \in \{0,1\} (0 \leq j \leq K-1)
  • 0 \leq \mathrm{seed} \leq 2^{60} - 1
  • 1 \leq M \leq \min(N, 10^5)
  • 0 \leq b_i \leq K-1 (1 \leq i \leq M)
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K \mathrm{seed} M
b_1 b_2 \cdots b_M
V_0 V_1 \cdots V_{K-1}

出力

K 行出力せよ。m 行目 (1 \leq m \leq K) には、k = m-1 のときの答えを出力せよ。


入力例 1

4 6 12233445577788999 4
4 2 4 1
1 1 0 0 1 0

出力例 1

2
0
1
2
1
2

この入力例において A = (4,2,4,1) です。

  • k = 0 のとき A' = (4,2,4,1) であり、このときの音節数は 2 です。
  • k = 1 のとき A' = (5,3,5,2) であり、このときの音節数は 0 です。
  • k = 2 のとき A' = (0,4,0,3) であり、このときの音節数は 1 です。
  • k = 3 のとき A' = (1,5,1,4) であり、このときの音節数は 2 です。
  • k = 4 のとき A' = (2,0,2,5) であり、このときの音節数は 1 です。
  • k = 5 のとき A' = (3,1,3,0) であり、このときの音節数は 2 です。

入力例 2

15 12 998154573227378904 2
5 6
0 0 1 1 0 1 0 0 1 1 0 1

出力例 2

4
4
3
3
3
4
4
4
3
3
3
4

この入力例において A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5) です。


入力例 3

7000000 15 409873722375451899 3
7 0 4
1 0 1 1 1 0 1 1 1 0 1 0 1 0 0

出力例 3

1680078
1681239
1679837
1680730
1680470
1679454
1679615
1679371
1681263
1679670
1680218
1680010
1680211
1680521
1681744

Score : 600 points

Problem Statement

There are K kinds of symbols numbered 0 to K-1.

Each symbol is either a vowel or not a vowel. If V_j = 1, symbol j is a vowel; if V_j = 0, symbol j is not a vowel.

Define the number of syllables of a symbol string as the number of maximal contiguous substrings of that string consisting of vowels. Formally, the number of syllables of a length-N symbol string (a_1, \dots, a_N) is defined as the number of pairs of integers (l,r) satisfying 1 \leq l \leq r \leq N and all of the following:

  • The symbols a_l, \dots, a_r are all vowels.
  • If l > 1, symbol a_{l-1} is not a vowel.
  • If r < N, symbol a_{r+1} is not a vowel.

You are given a length-N sequence A = (A_1, \dots, A_N). For each k = 0, \dots, K-1, answer the following question:

  • Define a length-N symbol string A' = (A'_1, \dots, A'_N) by A'_i := (A_i + k) \bmod K. What is the number of syllables of A'?

Input Format

The input for this problem is given in a special format.

Instead of A_1, \dots, A_N, the integers \mathrm{seed}, M, b_1, \dots, b_M are given from Standard Input. Restore A_1, \dots, A_N using the computation represented by the following pseudocode.

Here, all variables in the pseudocode are unsigned 64-bit integers. s \oplus t denotes the bitwise XOR of s and t, s \gg t denotes \lfloor s / 2^t \rfloor (the right shift operation), and s \ll t denotes s \times 2^t (the left shift operation).

\mathrm{state} \leftarrow \mathrm{seed}

for i = 1, \dots, N:
    if i \leq M:
        A_i \leftarrow b_i
    else:
        x \leftarrow \left( ((\mathrm{state} \gg 18) \oplus \mathrm{state}) \gg 27 \right) \bmod 2^{32}
        r \leftarrow \mathrm{state} \gg 59
        y \leftarrow \left( (x \gg r) + (x \ll (32-r)) \right) \bmod 2^{32}
        A_i \leftarrow y \bmod K
        \mathrm{state} \leftarrow (\mathrm{state} \times 6364136223846793005 + 2026081520260815) \bmod 2^{64}

Constraints

  • 1 \leq N \leq 7 \times 10^6
  • 1 \leq K \leq 2300
  • 0 \leq A_i \leq K-1 (1 \leq i \leq N)
  • V_j \in \{0,1\} (0 \leq j \leq K-1)
  • 0 \leq \mathrm{seed} \leq 2^{60} - 1
  • 1 \leq M \leq \min(N, 10^5)
  • 0 \leq b_i \leq K-1 (1 \leq i \leq M)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K \mathrm{seed} M
b_1 b_2 \cdots b_M
V_0 V_1 \cdots V_{K-1}

Output

Output K lines. The m-th line (1 \leq m \leq K) should contain the answer for k = m-1.


Sample Input 1

4 6 12233445577788999 4
4 2 4 1
1 1 0 0 1 0

Sample Output 1

2
0
1
2
1
2

In this input, A = (4,2,4,1).

  • For k = 0, A' = (4,2,4,1), and the number of syllables is 2.
  • For k = 1, A' = (5,3,5,2), and the number of syllables is 0.
  • For k = 2, A' = (0,4,0,3), and the number of syllables is 1.
  • For k = 3, A' = (1,5,1,4), and the number of syllables is 2.
  • For k = 4, A' = (2,0,2,5), and the number of syllables is 1.
  • For k = 5, A' = (3,1,3,0), and the number of syllables is 2.

Sample Input 2

15 12 998154573227378904 2
5 6
0 0 1 1 0 1 0 0 1 1 0 1

Sample Output 2

4
4
3
3
3
4
4
4
3
3
3
4

In this input, A = (5, 6, 0, 6, 8, 8, 8, 3, 0, 2, 3, 7, 3, 2, 5).


Sample Input 3

7000000 15 409873722375451899 3
7 0 4
1 0 1 1 1 0 1 1 1 0 1 0 1 0 0

Sample Output 3

1680078
1681239
1679837
1680730
1680470
1679454
1679615
1679371
1681263
1679670
1680218
1680010
1680211
1680521
1681744