시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2 | 2 | 2 | 100.000% |
You are given an array $A$ consisting of $N$ integers.
You are also given two integers $K$ and $L$.
You must divide the whole array $A$ into exactly $K$ nonempty intervals so that the length of each interval is not greater than $L$.
The cost of an interval $[S, E]$ is the bitwise XOR sum of all elements of $A$ whose indices are in $[S, E]$.
The score of a division is simply the maximum of the costs of all $K$ intervals in the division. You are interested in the best division: the one which minimizes the score of the division. Since this would be too simple for you, the problem is reversed.
You know the minimum score: the answer for the original problem is not greater than $X$. Now you want to know the maximum value of $K$.
The first line of input contains three integers $N$, $X$ and $L$ which are described above ($1 \le L \le N \le 10^5$, $0 \le X < 268\,435\,456$).
The next line contains three integers $A_{1}$, $P$ and $Q$ ($0 \le A_{1}, P, Q < 268\,435\,456$). All subsequent integers of the array $A$ are generated using these three integers in the following way: for every integer $1 < k \le N$, $A_{k} = (A_{k - 1} \cdot P + Q) \bmod 268\,435\,456$.
Print a single line containing the answer. If the answer does not exist, just print $0$.
3 1 2 1 1 1
2
3 0 3 1 1 1
1