No.896 More Than Friends, Less Than Lovers
Problem Statement
There are $N$ rabbits and $N$ kinds of eels.
The $j$-th rabbit considers an eel a friend if its Yukic◯der rating is a multiple of $a_j$, and considers an eel a lover if its rating is a multiple of $a_j \times b_j$.
There are $z_{x_i}$ eels with rating $x_i$.
For each rabbit, find the number of eels that are more than friends but less than lovers (that is, whose rating is a multiple of $a_j$ and not a multiple of $a_j \times b_j$).
($z_{x}$ = $\sum_{k: x_k=x} y_k$.
Consider that initially 0 eels have been found, and that each time $x_i$ $y_i$ is given as input, $y_i$ new eels with rating $x_i$ are found.)
Since Yukic◯der has a very large number of users, the input is generated by the following method.
(In the code below, X[i], Y[i], x[i], y[i], z[i], A[i], B[i], a[i], b[i] represent $X_i, Y_i, x_i, y_i, z_i, A_i, B_i, a_i, b_i$. for i in [L, R] means the same as for(int i = L; i <= R; i++).)
MOD is a power of 2 and can be written as MOD=$2^n$, and x % MOD can be computed as x & (MOD-1). (a%b is the remainder of a divided by b, and a&b is the bitwise and of a and b.)
The following is pseudocode of the algorithm that generates the input. Note that implementing the code below exactly as written may result in TLE or MLE.
(Holding $2^{24}$ 64-bit variables consumes 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]
Also, since the output would otherwise be too long, print the answers directly only for the first $M$ rabbits,
and on the last line print the exclusive OR of the answers of all rabbits.
Input
$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}$
The first line contains $M$ $N$ $mulX$ $addX$ $mulY$ $addY$ $MOD$.
The second line contains $M$ input values $X_i$.
The third line contains $M$ input values $Y_i$.
The fourth line contains $M$ input values $A_i$.
The fifth line contains $M$ input values $B_i$.
All input values are integers.
$1$ $\le$ $M$ $\le$ $10^3$
$M$ $\le$ $N$ $\le$ $10^7$
$1$ $\le$ $MOD$ $\le$ $2^{24}$ ($MOD$ is a power of 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$
Output
Output $M+1$ lines.
On the $j$-th of the first $M$ lines, print the number of eels that are more than friends but less than lovers for rabbit $j$, followed by a newline.
On line $M+1$, print the exclusive OR of the answers of all rabbits, followed by a newline.
Sample
Sample 1
Input
3 3 0 0 0 0 8 4 4 4 1 2 3 1 2 3 2 3 1
Output
0 6 0 6
There are 6 eels with rating 4.
For the 1st rabbit, all eels are both friends and lovers.
For the 2nd rabbit, all eels are more than friends but less than lovers.
For the 3rd rabbit, all eels are neither friends nor lovers.
Sample 2
Input
2 2 1 2 3 4 8 0 1 1 0 1 2 2 1
Output
0 0 0
0 is a multiple of every integer.
Sample 3
Input
1 10 1 1 1 1 32 1 2 3 4
Output
21 13
Sample 4
Input
1 8 5 3 0 2 16 1 5 2 6
Output
6 15
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Lepton_s
37zigen