Advanced L: Counting Grids Again

Is there a greedy that determines the optimal independent set?

How can we make the $$$K$$$ grids "independent"?

Think game theory. What does the graph also represent?

We can first notice that choosing the independent set can be done greedily from maximum to minimum $$$S$$$ due to $$$NM^{K \cdot S} \gt NM^{K \cdot (S-1)} (NM^K - 1)$$$. The issue now is the large value of $$$K$$$, which calls for finding a way to think of each of the $$$K$$$ boards independently. To do this, consider the following two player-game:

Initially, each grid, numbered $$$1$$$ to $$$K$$$, has one token on one of the cells. Alice and Bob take turns alternately. On each player's turn, the current player chooses some grid $$$G$$$ $$$(1 \leq G \leq K)$$$ and moves the token on cell $$$(i, j)$$$ and moves it to either $$$(k, j)$$$ $$$(0 \leq k \lt i)$$$ or $$$(i, k)$$$ $$$(0 \leq k \lt j)$$$ on grid $$$G$$$. Note that this is equivalent to traversing the graph with each move moving closer to $$$((0, 0), \dots, (0, 0))$$$. The current player loses when they cannot move.

The key realization here is that the game states in which the current player is losing is exactly our desired independent set in the graph. Because there are $$$K$$$ disjoint boards in the setting of a game, we can now think of each token position as some Grundy number. Let $$$\text{SG}(i, j)$$$ be the Grundy number if the token is at $$$(i, j)$$$. From this transformation, we see that a node $$$(P_1, P_2, \dots, P_K)$$$ is in our desired independent set if and only if $$$\text{SG}(P_1) \oplus \text{SG}(P_2), \cdots, \text{SG}(P_{K-1})\oplus \text{SG}(P_K) = 0$$$, where $$$\oplus$$$ is the bitwise XOR operator.

We can then let

Now, denoting the $$$\oplus$$$ convolution operator as $$$*$$$, the answer is $$$(\underbrace{C * ... * C}_{\text{K times}})_0$$$. Naive binary exponentiation can compute this in $$$\mathcal{O}((N + M)^2 \log K)$$$ given that $$$\max(SG(i, j))$$$ scales on the order of $$$\mathcal{O}(N + M)$$$.

These are already some very tough observations, but this still only gets $$$60/100$$$ points. There are still two more key parts to achieve a full solution.

The first part is to optimize calculating Grundy numbers of each cell, in which a naive solution takes $$$\mathcal{O}(NM (N + M))$$$. If we write a brute force and look for patterns, what we find is that $$$\text{SG}(i, j) = i \oplus j$$$. This can be proven by induction by showing that if this property holds for all cells in the square $$$((0, 0), (2^k-1, 2^k-1))$$$, then it also holds for all values in the square $$$((0, 0), (2^{k+1}-1, 2^{k+1}-1))$$$. The full proof is left as an exercise for the reader.

The second part is to optimize the $$$\oplus$$$ convolution. To do this, we must use $$$\oplus$$$ $$$\text{FWHT}$$$ (Fast Walsh–Hadamard transform). Denoting $$$\text{FWHT}$$$ as $$$F$$$ for short, we note that $$$C * C = F^{-1}(F(C) \cdot F(C))$$$. Applying $$$\text{FWHT}$$$ naively with binary exponentiation obtains an $$$\mathcal{O}((N + M) \log (N + M)\log K)$$$ solution.

However, we can make this faster by more closely analyzing the convolution.

Canceling the $$$F$$$ and $$$F^{-1}$$$, we get

From this, by induction, we can notice that $$$\underbrace{C * ... * C}_{\text{K times}} = F^{-1}\left(F(C)^K\right)$$$. This allows us to use binary exponentiation on each index of $$$C$$$ and only $$$2$$$ calls of $$$\text{FWHT}$$$, solving the problem in $$$\mathcal{O}((N + M) \cdot (\log (N + M) + \log K))$$$.

#include "bits/stdc++.h"
using namespace std;

constexpr int mod = 998244353, inv2 = (mod + 1) / 2;
typedef long long ll;

int add(int x, int y) {
    if (x + y >= mod) return x + y - mod;
    if (x + y < 0) return x + y + mod;
    else return x + y;
}

int mul(int x, int y) {
    return (ll)x * y % mod;
}

int power(int x, int p) {
    int res = 1;
    while (p) {
        if (p & 1) res = mul(res, x);
        x = mul(x, x);
        p >>= 1;
    }

    return res;
}

void FWHT(vector<int> &a, bool inv = false) {
    int sz = a.size();
    for (int len = 1; 2 * len <= sz; len <<= 1) {
        for (int i = 0; i < sz; i += 2 * len) {
            for (int j = i; j < i + len; j++) {
                int x = a[j], y = a[j + len];
                if (!inv) a[j] = add(x, y), a[j + len] = add(x, -y);
                else a[j] = mul(add(x, y), inv2), a[j + len] = mul(add(x, -y), inv2);
            }
        }
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x = n * m, y = 1;
    while (y < x) y <<= 1;
    int v = power(x, k);
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> f(y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            f[i ^ j] = add(f[i ^ j], power(v, a[i][j]));
        }
    }

    FWHT(f);
    for (int i = 0; i < y; i++) {
        f[i] = power(f[i], k);
    }

    FWHT(f, 1);
    cout << f[0] << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}