PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary exponentiation
PROBLEM:
For a cyclic array A, define f(A) as the cyclic array B such that B_i = A_{i-1} \oplus A_i \oplus A_{i+1}.
Given N and K, count the number of arrays A of length N with elements in [0, 2^K-1] such that f^{2^K}(A) contains only zeros.
EXPLANATION:
The array transformation involves only bitwise XOR, and hence operates completely independently on different bits.
This allows us to simply solve the problem for boolean arrays, and then raise that count to the K-th power to account for K bits.
Let’s now focus on solving the problem for boolean arrays, i.e. each element is either 0 or 1.
Naturally, the first thing to do is to figure out what exactly f^{2^K}(A) looks like.
Let’s look specifically at f^{2^K}(A)_i, i.e. the i-th element of the array, and see how it changes with respect to K.
Observe that f^{2^K}(A) = f^{2^{K-1}}(f^{2^{K-1}}(A)).
This is a useful property to keep in mind.
Working out a couple of small examples, it can be seen that:
- f^1(A)_i = A_{i-1} \oplus A_i \oplus A_{i+1}, by definition.
- f^2(A)_i = A_{i-2} \oplus A_i \oplus A_{i+2}
This is because the terms A_{i-1} and A_{i+1} will appear twice each in the expression and hence cancel out; while A_i appears thrice and A_{i-2}, A_{i+2} appear once each.
Recall that x\oplus x = 0 so anything that appears an even number of times cancels out while anything that appears an odd number of times is equivalent to appearing once. - f^4(A)_i = f^2(f^2(A))_i = A_{i-4} \oplus A_i \oplus A_{i+4}
\vdots
In general, we have the nice property that for any index i and parameter K \ge 0,
Of course, the indices are being considered cyclically here.
This is fairly easy to prove via induction: for K = 0 it’s true by definition of the operation, and for K \ge 1 it can be proved by taking the result for K-1 and noting that the terms A_{i-2^{K-1}} and A_{i+2^{K-1}} cancel out in the resulting expression (essentially the same thing that happened when computing f^2(A)_i earlier.)
Let’s now use the above characterization to solve the problem.
We want f^{2^K}(A)_i = 0 for all i.
This means we want A_i \oplus A_{i-2^K} \oplus A_{i+2^K} = 0 for all i.
This is possible if and only if either all of these three elements are 0, or exactly one of them is 0.
Further, note that this puts the elements \ldots, A_{i-2^K}, A_i, A_{i+2^K}, A_{i+2\cdot 2^K}, \ldots into a cycle where they all depend on each other.
More precisely, starting from any index i and repeatedly jumping 2^K steps cyclically till you eventually end up back at i gives us a single cycle of elements that depend on each other.
(Note that the jumps being constant length means we will in fact end up back at i, and also this will be the first time we visit a previously-visited index.)
This partitions the indices [1, N] into several cycles, and each cycle is independent of the others so we can try to solve for a single cycle.
First, clearly one solution is to just make every element on the cycle 0, so what we instead look for is non-trivial solutions that contain at least one occurrence of 1.
However, if we place a 1 at all, it can be verified that the only possible solution (upto cyclic shifts) is the pattern
This is because each occurrence of 1 needs to have a 0 and a 1 as its neighbors; and if we have two consecutive occurrences of 0 then we’ll have either 100 or 001 appear, both of which are bad patterns - which forces both neighbors of a 0 to be 1’s.
Now, this pattern repeats itself every three steps.
So,
- If the length of the cycle is not a multiple of 3, then it’s impossible to satisfy this pattern.
So, in this case the only possible solution is for every element to be 0. - If the length of the cycle is a multiple of 3, then it is possible to satisfy the pattern; further, there are exactly three distinct ways to do it since it has three possible cyclic shifts.
Along with the all-zeros solution, we thus have 4 ways to assign elements to the cycle.
Thus, each cycle of indices has either 1 or 4 possible solutions, depending on its length modulo 3.
To complete the solution, we thus need to know the count of cycles whose lengths are multiples of 3.
Luckily, this is much easier than it sounds - because every cycle has the same length!
It is a well-known fact from elementary number theory that when working with residues modulo N, if we fix a parameter M and create equivalence classes under the relation of x being related to x+M,
- There are exactly \gcd(N, M) equivalence classes, with representatives 0, 1, 2, \ldots, \gcd(N, M)-1
- Each equivalence class has size N / \gcd(N, M).
If you’re unfamiliar with this conclusion, read this blog, specifically the section on additive structure of residues modulo N.
Applying this to our situation, we thus have \gcd(N, 2^K) cycles, each with length \displaystyle \frac{N}{\gcd(N, 2^K)}.
So,
- If \frac{N}{\gcd(N, 2^K)} is a multiple of 3, each cycle has 4 choices.
With \gcd(N, 2^K) cycles, the total count becomes 4^{\gcd(N, 2^K)} - Otherwise, each cycle has only one choice (all zeros).
The total count is simply 1.
Finally, all of this was to solve for only a single bit.
There are K bits, so the final answer is obtained by raising the previously obtained value to the K-th power.
TIME COMPLEXITY:
\mathcal{O}(\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 998244353
import math
for _ in range(int(input())):
n, k = map(int, input().split())
ct = math.gcd(n, 2**k)
cyc = n // ct
if cyc%3 == 0: print(pow(4, ct*k, mod))
else: print(1)