GCDXOR2 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: hjroh0315
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic programming

PROBLEM:

You’re given N and D. Count the number of pairs of integers (X, Y) such that:

  1. 1 \leq X \leq Y \lt 2^N
  2. \gcd(X, Y) = X\oplus Y
  3. Y-X = D

N \leq 60 and D \leq 2000 in this version.

EXPLANATION:

We have several different quantities to work with here: the difference, \gcd, and bitwise XOR of X and Y.
Let’s work out some relations between them.

First, we have \gcd(X, Y) = \gcd(X, Y-X) \leq Y-X.

We also have X\oplus Y \geq Y-X, obtained by looking at the binary representation of both sides:

  • If some bit is set or unset in both X and Y, it doesn’t contribute to either the difference or the XOR.
  • If some bit b is set in only one of X and Y, it contributes 2^b to the XOR but either 2^b or 2^{-b} to the difference; so the XOR cannot be smaller either way.

In particular, seeing it this way tells us that X\oplus Y = Y - X happens if and only if, for each bit that’s set in X\oplus Y, it’s set in Y but not in X.

Now, we want \gcd(X, Y) = X\oplus Y.
From above, we know \gcd(X, Y) \leq Y-X \leq X\oplus Y, so the only way these two can be equal is if they also equal the difference between X and Y.
Note that this difference is given to us, and equals D.

However, we also know what it means for the difference to equal the XOR: the bits of the difference D must be set in Y and unset in X; and all other bits must be either set or unset in both values.

So, let’s start with X = 0 and Y = D.
Now, for every bit not set in D, we need to decide whether to set it or not in both X and Y.
Note that no matter what the choice is, the XOR and difference of X and Y remains D, so those conditions we no longer need to worry about: the only issue is ensuring \gcd(X, Y) = D.

For this, we certainly need to make X and Y be multiples of D; and since their difference equals D, this is also sufficient for their GCD to equal exactly D.

We now have a much reduced problem: we’d like to know the number of ways to choose a subset of bits from [0, N-1], excluding those already set in D, while ensuring that both X and Y are multiples of D.
Note that starting with X = 0 and Y = D makes them already multiples of D, so we’re really looking for the number of subsets of these bits that also give multiples of D.

This is fairly straightforward to do, using dynamic programming.

Let’s define dp[i][r] to be the number of subsets of bits \{0, 1, 2, \ldots, i\} such that the remainder of the subset is r modulo D.
Then,

  • If i is set in D, dp[i][r] = dp[i-1][r].
  • Otherwise, dp[i][r] = dp[i-1][r] + dp[i-1][(r - 2^i) \bmod D] since we can either take or not take bit i.

The answer we’re looking for is then dp[N-1][0].
Note that the base case here is along the lines of dp[-1][0] = 1 (to account for the empty set), so we should subtract 1 from this in the end to discard this case: after all, choosing the empty set corresponds to the (X, Y) pair of (0, D), which is not allowed since we want values to be positive.

It’s also of course possible to use \mathcal{O}(D) memory rather than \mathcal{O}(ND), though the constraints here are so small that this doesn’t matter at all.

TIME COMPLEXITY:

\mathcal{O}(ND) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n, d = map(int, input().split())
    
    dp = [0]*d
    dp[0] = 1
    for b in range(n):
        if d & (1 << b): continue
        val = (1 << b) % d
        
        ndp = [0]*d
        for i in range(d):
            ndp[(i + val) % d] = (dp[i] + dp[(i + val) % d]) % mod
        dp = ndp[:]
    print(dp[0] - 1)
2 Likes