This is the first Handwritten solution for certain problem 3393. Count Paths With the Given XOR Value. It is necessary to understand the state-transition equation.
The problem statement:
You are given a 2D integer array grid with size m x n. You are also given an integer k.
Your task is to calculate the number of paths you can take from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) satisfying the following constraints:
1. You can either move to the right or down. Formally, from the cell (i, j) you may move to the cell (i, j + 1) or to the cell (i + 1, j) if the target cell exists.
2. The XOR of all the numbers on the path must be equal to k.
Return the total number of such paths.
Since the answer can be very large, return the result modulo 10^9 + 7.
It shows that the XOR is reversible then x^y = k implies that x^y^y = k^y and x = k^y which finally gets to the equation
\(f[i+1][j+1][x] = f[i+1][j][x\oplus grid[i][j]]+ f[i+1][j+1][x\oplus grid[i][j]]\)
Where the final solution should be
class Solution {
public:
int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
const int MOD = 1'000'000'007;
int mx = 0;
for (auto& row : grid) {
mx = max(mx, ranges::max(row));
}
int u = 1 << bit_width((unsigned) mx);
if (k >= u) {
return 0;
}
int m = grid.size(), n = grid[0].size();
vector f(m + 1, vector(n + 1, vector<int>(u)));
f[0][1][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int val = grid[i][j];
for (int x = 0; x < u; x++) {
f[i + 1][j + 1][x] = (f[i + 1][j][x ^ val] + f[i][j + 1][x ^ val]) % MOD;
}
}
}
return f[m][n][k];
}
};
Overall, one should think of the enumeration method to obtain all the result! From the maximum bit width shift in the bit-wise operation, we could learn from int u = 1 << bit_width((unsigned) mx); to work on the bit shift.