Идея: все условия — это линейные уравнения над полем GF(2), потому что XOR — это сложение по модулю 2.

Количество подходящих матриц равно:

$$2^{\text{число свободных переменных}}$$

Всего переменных:

$$nm$$

Нужно понять, сколько независимых условий дают все r × c подматрицы.

Ответ:

$$2^{nm-(n-r+1)(m-c+1)}$$

по модулю 998244353.

Код:

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll mod = 998244353;

ll binpow(ll a, long long b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        ll n, m, r, c;
        cin >> n >> m >> r >> c;

        ll x = n * m;
        ll y = (n - r + 1) * (m - c + 1);
        ll d = x - y;

        cout << binpow(2, d) << '\n';
    }

    return 0;
}

Почему это работает:

Матрица состоит из n * m битов. Каждый бит — переменная: 0 или 1.

Для каждой подматрицы r × c есть условие:

$$a_{i,j} \oplus a_{i,j+1} \oplus \dots = 0$$

Это линейное уравнение над GF(2).

Всего таких подматриц:

$$(n-r+1)(m-c+1)$$

Главный факт: все эти уравнения независимы.

Почему независимы?

Сначала посмотрим на одномерный случай. Например, есть строка длины m, и мы берём все отрезки длины c.

Матрица условий выглядит так:

text
11100...
01110...
00111...
...

Каждая новая строка начинается с новой позиции. Поэтому у каждой строки есть свой первый ненулевой элемент, которого не было у предыдущих строк. Значит, эти строки линейно независимы.

Для двумерного случая каждое условие r × c — это произведение вертикального условия на горизонтальное. Ранг такой системы равен:

$$(n-r+1)(m-c+1)$$

То есть каждое окно r × c действительно добавляет одно новое независимое ограничение.

Тогда число свободных переменных:

$$nm-(n-r+1)(m-c+1)$$

Каждую свободную переменную можно выбрать двумя способами: 0 или 1.

Значит:

$$ans = 2^{nm-(n-r+1)(m-c+1)}$$

Так как числа огромные, считаем степень быстрым бинарным возведением в степень за O(log(nm)).

Сложность:

$$O(t \log(nm))$$

при t ≤ 10000 это легко проходит за 1 секунду.

Что изучить, чтобы решать такие задачи:

1. XOR как сложение по модулю 2.
2. Линейная алгебра над GF(2).
3. Системы линейных уравнений и число решений.
4. Ранг матрицы.
5. Независимость условий.
6. Быстрое возведение в степень.
7. Задачи на “количество бинарных объектов при XOR-ограничениях”.

Где тренироваться:

Codeforces:

• задачи с тегами xor, linear algebra, math, constructive algorithms;
• отдельно полезно порешать задачи на Gaussian elimination over GF(2).

Темы для поиска лекций:

• “XOR basis Codeforces”
• “Linear algebra over GF(2)”
• “Gaussian elimination mod 2”
• “Rank nullity theorem”
• “Counting solutions of linear equations over finite fields”

Главный шаблон для таких задач:

Если есть k бинарных переменных и rank независимых XOR-условий, то количество решений:

$$2^{k-rank}$$

Ниже два решения. Вторая задача легче, особенно если плохо с битовыми операциями. Первая требует понять XOR-игру и проигрышные позиции.

---

Задача 1

Код C++

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<ll> a(n);
        ll x = 0;

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            x ^= a[i];
        }

        if (n == 1) {
            cout << 0 << '\n';
            continue;
        }

        ll ans = 0;

        if (x == 0) ans++;

        for (int i = 0; i < n; i++) {
            ll y = x ^ a[i];
            if (y < a[i]) ans++;
        }

        cout << ans % mod << '\n';
    }

    return 0;
}

---

Идея задачи 1

Игрок выбирает массив b, такой что:

$$0 \le b_i \le a_i$$ $$b_1 \oplus b_2 \oplus \dots \oplus b_n = 0$$

и хотя бы один b_i > 0.

Потом массив становится:

$$a_i := a_i - b_i$$

То есть после хода остаётся некоторый массив s, где:

$$s_i = a_i - b_i$$

Нам нужно посчитать ходы Алисы, после которых Боб окажется в проигрышной позиции.

---

Какие позиции проигрышные?

Проигрышные позиции — это позиции, где не больше одного ненулевого числа.

Например:

text
[0, 0, 0]
[5, 0, 0]
[0, 7, 0]
[0, 0, 10]

Почему?

Если ненулевое число только одно, например:

text
[5, 0, 0]

то любой ненулевой ход должен выбрать b, у которого XOR равен 0.

Но если можно уменьшать только одно число, то выбранный b будет выглядеть так:

text
[x, 0, 0]

А XOR будет равен x.

Чтобы XOR был 0, нужно x = 0, но такой ход запрещён.

Значит, ходов нет.

А если ненулевых чисел хотя бы два, то можно сделать ход так, чтобы оставить не больше одного ненулевого числа. Поэтому такая позиция выигрышная.

---

Что нужно посчитать?

После первого хода Алисы должен остаться массив s, в котором не больше одного ненулевого числа.

То есть возможны два случая.

---

Случай 1

После хода остаётся всё нулевое:

text
[0, 0, 0, ..., 0]

Тогда Алиса забрала весь массив:

$$b_i = a_i$$

Такой ход допустим только если:

$$a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$$

В коде общий XOR называется x.

Если x == 0, добавляем 1 к ответу.

cpp
if (x == 0) ans++;

---

Случай 2

После хода остаётся ровно одно ненулевое число.

Пусть оно остаётся на позиции i.

Тогда после хода:

text
s_i = some positive value
s_j = 0 для всех j != i

То есть Алиса забирает полностью все элементы, кроме i.

Обозначим:

$$y = b_i$$

Тогда XOR выбранного массива b должен быть равен 0.

XOR всех a_i равен x.

Если на позиции i мы вместо a_i берём y, то XOR массива b будет:

$$x \oplus a_i \oplus y$$

Нужно:

$$x \oplus a_i \oplus y = 0$$

Отсюда:

$$y = x \oplus a_i$$

В коде:

cpp
ll y = x ^ a[i];

Теперь нужно, чтобы Алиса действительно что-то оставила на позиции i.

То есть:

$$b_i < a_i$$

А значит:

$$y < a_i$$

Если это выполнено, такой ход подходит:

cpp
if (y < a[i]) ans++;

---

Почему отдельно n == 1?

Если массив длины 1, то ход должен выбрать b1, и при этом:

$$b_1 = 0$$

потому что XOR из одного числа равен самому числу.

Но ненулевой ход запрещён. Значит, ходов вообще нет.

cpp
if (n == 1) {
    cout << 0 << '\n';
    continue;
}

---

Задача 2

Код C++

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, d;
        cin >> n >> d;

        vector<ll> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<ll> b(3 * n);

        for (int i = 0; i < 3 * n; i++) {
            b[i] = a[i % n];
        }

        vector<ll> p(3 * n + 1, 0);

        for (int i = 0; i < 3 * n; i++) {
            p[i + 1] = p[i] + b[i];
        }

        ll ans = 0;

        for (int i = 0; i < n; i++) {
            int j = i + n;

            ll l = p[j] - p[j - d];
            ll r = p[j + d + 1] - p[j + 1];

            ll s = l + r;
            ll cur = 2LL * d * a[i] - s;

            if (cur > 0) ans += cur;
        }

        cout << ans << '\n';
    }

    return 0;
}

---

Идея задачи 2

Каждый человек либо получает подарок, либо нет.

Обозначим:

text
g_i = 1, если человек i получил подарок
g_i = 0, если не получил

Рассмотрим двух людей i и j, которые видят друг друга.

Есть 4 случая.

---

Оба получили подарок

text
g_i = 1
g_j = 1

Никто не видит человека без подарка.

Вклад пары:

$$0$$

---

Оба не получили подарок

text
g_i = 0
g_j = 0

Никто не видит человека с подарком.

Вклад пары:

$$0$$

---

i получил подарок, j не получил

Тогда человек i получает:

$$+a_i$$

А человек j теряет:

$$-a_j$$

Итог:

$$a_i - a_j$$

---

j получил подарок, i не получил

Итог:

$$a_j - a_i$$

---

Главный вывод

Для каждой пары видящих друг друга людей выгодно, чтобы подарок получил человек с большим весом.

Но один человек участвует во многих парах, поэтому нужно аккуратно посчитать общий вклад.

Для пары i, j вклад можно записать так:

$$(a_i - a_j)(g_i - g_j)$$

Проверим:

Если g_i = 1, g_j = 0:

$$(a_i - a_j)(1 - 0) = a_i - a_j$$

Если g_i = 0, g_j = 1:

$$(a_i - a_j)(0 - 1) = a_j - a_i$$

Если одинаково:

$$g_i - g_j = 0$$

значит вклад 0.

---

Почему задача становится простой?

Общая сумма:

$$\sum (a_i - a_j)(g_i - g_j)$$

Можно раскрыть скобки.

Для каждого человека i получится некоторый коэффициент:

$$coef_i = 2d \cdot a_i - \text{сумма весов всех людей в поле зрения i}$$

Тогда итоговое счастье:

$$coef_1 g_1 + coef_2 g_2 + \dots + coef_n g_n$$

Теперь каждый g_i выбирается независимо.

Если:

$$coef_i > 0$$

то выгодно дать подарок человеку i.

Если:

$$coef_i \le 0$$

то выгодно не давать.

Ответ:

$$\sum \max(0, coef_i)$$

---

Как быстро найти сумму людей в поле зрения?

Люди сидят по кругу.

Для человека i надо взять:

• d человек слева;
• d человек справа.

Чтобы не мучиться с переходом через конец массива, делаем массив длины 3n.

Например:

text
a = [5, 2, 7]

b = [5, 2, 7, 5, 2, 7, 5, 2, 7]

Центральная копия массива начинается с индекса n.

Поэтому человек i в центральной копии имеет индекс:

cpp
int j = i + n;

Сумму слева берём так:

cpp
ll l = p[j] - p[j - d];

Сумму справа так:

cpp
ll r = p[j + d + 1] - p[j + 1];

p — массив префиксных сумм.

---

Какая задача легче?

Вторая задача легче.

Почему:

• там почти нет битовых операций;
• нужно понять вклад пары людей;
• потом задача превращается в префиксные суммы;
• алгоритм более стандартный.

Первая задача сложнее, потому что там надо понять:

• XOR;
• игру;
• проигрышные позиции;
• почему нужно считать переходы именно в позиции с не более чем одним ненулевым числом.

Если у тебя проблемы с битовыми операциями, сначала лучше разбирать задачу 2.

---

Что учить

Для задачи 1:

1. XOR.
2. Свойства XOR: $$x \oplus x = 0$$ $$x \oplus 0 = x$$ $$x \oplus y = y \oplus x$$
3. Nim-игры.
4. Выигрышные и проигрышные позиции.
5. Impartial games.
6. Sprague-Grundy — позже, не сразу.
7. Задачи Codeforces по тегам:
   • bitmasks
   • xor
   • games

Для задачи 2:

1. Префиксные суммы.
2. Круговые массивы.
3. Линейность суммы.
4. Раскрытие скобок.
5. Жадный выбор по коэффициенту.
6. Задачи Codeforces по тегам:
   • prefix sums
   • greedy
   • math

Что посмотреть:

• e-maxx / cp-algorithms: Prefix sums.
• cp-algorithms: Bit manipulation.
• Codeforces EDU: Bitmasks.
• YouTube: “XOR for competitive programming”.
• YouTube: “Nim game explanation”.
• YouTube: “Prefix sums competitive programming”.

С чего начать практику:

1. Сначала обычные префиксные суммы.
2. Потом круговые массивы.
3. Потом простые XOR-задачи.
4. Потом Nim.
5. Потом задачи на XOR + игры.