No.896 友達以上恋人未満

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 198 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : Lepton_sLepton_s / テスター : 37zigen37zigen
1 ProblemId : 2101 / 出題時の順位表

問題文

$N$ 匹のうさぎと、$N$ 種類のうなぎがいます。
$j$ 番目のうさぎは Yukic◯derのレーティングが $a_j$ の倍数であるようなうなぎを友達だと思っていて、$a_j \times b_j$ の倍数であるようなうなぎを恋人だと思っています。
レーティングが $x_i$ であるうなぎは $z_{x_i}$ 匹います。
各うさぎについて、友達以上恋人未満である (すなわち、レーティングが $a_j$ の倍数であり、$a_j \times b_j$ の倍数でない) ようなうなぎの匹数を求めてください。

($z_{x}$ = $\sum_{k: x_k=x} y_k$ と表されます。
最初の状態ではうなぎが 0 匹見つかっていて、入力として $x_i$ $y_i$ が与えられる度に、レーティング $x_i$ のうなぎが新しく $y_i$ 匹見つかると考えてください。)

Yukic◯der はユーザ数がとても多いため、以下の方法で入力を生成します。
(以下のコード中の X[i], Y[i], x[i], y[i], z[i], A[i], B[i], a[i], b[i] は $X_i, Y_i, x_i, y_i, z_i, A_i, B_i, a_i, b_i$ を表しています。for i in [L, R] は for(int i = L; i <= R; i++) と同じ意味です。)
MOD は 2 冪で、MOD=$2^n$と表すことができ、x % MODは、x & (MOD-1) で計算できます。(a%b は a を b で割った余り、 a&b は a と b の bitwise and とする。)
以下が入力を生成するアルゴリズムの擬似コードです。以下のコードを全くそのまま実装すると TLE または MLE する可能性があることに注意してください。 (64 bit の変数を $2^{24}$個保持すると、 128 MB を消費します。)

z[0] = z[1] = ... = z[MOD-1] = 0
for i in [1, M]:
    x[i] = X[i]
    y[i] = Y[i]
    a[i] = A[i]
    b[i] = B[i]
    
for i in [M+1, N]:
    x[i] = (x[i-1] * mulX + addX) % MOD
    y[i] = (y[i-1] * mulY + addY) % MOD
    a[i] = (a[i-1] * mulX + addX + MOD - 1) % MOD + 1
    b[i] = (b[i-1] * mulY + addY + MOD - 1) % MOD + 1

for i in [1, N]:
    z[x[i]] += y[i]
また、出力の行数も長くなってしまうため、最初の $M$ 匹のうさぎに関しては、答えをそのまま出力し、 最後の行に、すべてのうさぎの答えの排他的論理和を取った値を出力してください。

入力

$M$ $N$ $mulX$ $addX$ $mulY$ $addY$ $MOD$
$X_1$ $\cdots$ $X_{M}$
$Y_1$ $\cdots$ $Y_{M}$
$A_1$ $\cdots$ $A_{M}$
$B_1$ $\cdots$ $B_{M}$

1 行目に $M$ $N$ $mulX$ $addX$ $mulY$ $addY$ $MOD$ が与えられます。
2 行目に $M$ 個の入力 $X_i$ が与えられます。
3 行目に $M$ 個の入力 $Y_i$ が与えられます。
3 行目に $M$ 個の入力 $A_i$ が与えられます。
4 行目に $M$ 個の入力 $B_i$ が与えられます。
入力はすべて整数です。

$1$ $\le$ $M$ $\le$ $10^3$
$M$ $\le$ $N$ $\le$ $10^7$
$1$ $\le$ $MOD$ $\le$ $2^{24}$ ($MOD$ は 2 冪)
$0$ $\le$ $mulX$, $addX$, $mulY$, $addY$ $\lt$ $MOD$
$0$ $\le$ $X_i$, $Y_i$ $\lt$ $MOD$
$1$ $\le$ $A_j$, $B_j$ $\le$ $MOD$

出力

$M+1$ 行の出力があります。
最初の $M$ 行のうち、$j$ 行目にはうさぎ $j$ にとって友達以上恋人未満であるようなうなぎの匹数を出力し、改行してください。
$M+1$ 行目にすべてのうさぎの答えの排他的論理和を出力し、改行してください。

サンプル

サンプル1
入力
3 3 0 0 0 0 8
4 4 4
1 2 3
1 2 3
2 3 1
出力
0
6
0
6

レーティングが 4 のうなぎが 6 匹います。
1番目のうさぎにとって、すべてのうなぎは友達かつ恋人です。
2番目のうさぎにとって、すべてのうなぎは友達以上恋人未満です。
3番目のうさぎにとって、すべてのうなぎは友達でも恋人でもありません。

サンプル2
入力
2 2 1 2 3 4 8
0 1
1 0
1 2
2 1
出力
0
0
0

0 はすべての整数の倍数です。

サンプル3
入力
1 10 1 1 1 1 32
1
2
3
4
出力
21
13

サンプル4
入力
1 8 5 3 0 2 16
1
5
2
6
出力
6
15

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。