题目解析

给定一个长度为 $n$ 的数组 $a$（$0 \le a_i \le 50$），有 $q$ 个询问，每个询问给出区间 $[l, r]$。
在区间内，Ruslan 可以移除任意多个堆（至少保留一堆），使得剩余堆的石子数的 XOR 为 $0$（这样 Artem 先手会输）。
Ruslan 希望移除尽可能多的堆，并计算达到这个最大移除数的方案数（对 $998244353$ 取模）。如果无法使 XOR 为 $0$，输出 -1。

关键观察

1. Nim 的胜利条件

在 Nim 游戏中，先手必败当且仅当所有堆的石子数 XOR 为 $0$。
因此我们需要移除一些堆，使得剩余堆的 XOR 为 $0$。

2. 同值的堆

对于某个值 $x$，在区间内出现 $c$ 次。

• 移除偶数个 $x$，XOR 不变（因为偶数个 $x$ 异或为 $0$）。
• 移除奇数个 $x$，XOR 会异或上 $x$。

因此，保留的 $x$ 的个数要么是 $0$、$1$、$2$（保留更多没有意义，因为可以再移除 $2$ 个而不改变 XOR，从而移除更多堆）。
实际上，我们只需考虑保留 $0$、$1$ 或 $2$ 个 $x$。

3. 动态规划状态

我们按值 $0$ 到 $50$ 依次处理。
定义 $dp[i][xor][f]$：

• 已经处理了值 $0 \dots i-1$
• 当前保留堆的 XOR 为 $xor$
• $f = 1$ 表示已经至少保留了一堆，$f = 0$ 表示还没有保留任何堆
• 存储一个 (最大移除数, 方案数) 对。

4. 转移

对于当前值 $x$，出现次数 $c$：

• 保留 $0$ 个：移除全部 $c$ 个，XOR 不变，$f$ 不变，移除数增加 $c$，方案数乘 $1$。
• 保留 $1$ 个：从 $c$ 个中选 $1$ 个保留，移除 $c-1$ 个，XOR 异或上 $x$，$f$ 变为 $1$，方案数乘 $c$。
• 保留 $2$ 个：从 $c$ 个中选 $2$ 个保留，移除 $c-2$ 个，XOR 不变（因为 $x \oplus x = 0$），$f$ 变为 $1$，方案数乘 $\binom{c}{2}$。

5. 初始与答案

• 初始：$dp[0][0][0] = (0, 1)$，其余为 $(-1, -1)$。
• 最终答案：$dp[51][0][1]$，即处理完所有值后，XOR 为 $0$ 且至少保留了一堆。

若 $dp[51][0][1].cnt = -1$，输出 -1；否则输出最大移除数和方案数。

时间复杂度

状态数：$51 \times 64 \times 2 = 6528$。
每个状态转移 $3$ 次，总 $O(51 \cdot 64 \cdot 2 \cdot 3) \approx 2 \times 10^4$ 每查询，$q \le 10^5$ 时可接受（实际常数优化后可行）。

C++ 代码实现

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

const int MOD = 998244353;
const int MAX_VAL = 50;

int add(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int mul(int a, int b) {
    return (long long)a * b % MOD;
}

struct State {
    int mx, cnt;
};

State dp[MAX_VAL + 2][64][2];

void merge(State &a, int mx, int cnt) {
    if (a.mx > mx) return;
    if (a.mx < mx) {
        a.mx = mx;
        a.cnt = 0;
    }
    a.cnt = add(a.cnt, cnt);
}

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

    int n, q;
    cin >> n >> q;

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

    int max_val = *max_element(a.begin(), a.end());

    // 前缀计数
    vector<vector<int>> cnt(n + 1, vector<int>(max_val + 1, 0));
    for (int i = 0; i < n; i++) {
        cnt[i + 1] = cnt[i];
        cnt[i + 1][a[i]]++;
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;

        // 初始化 dp
        memset(dp, -1, sizeof(dp));
        dp[0][0][0] = {0, 1};

        for (int v = 0; v <= max_val; v++) {
            int c = cnt[r][v] - cnt[l][v];
            if (c == 0) {
                // 没有这个值，直接复制状态
                for (int xor_val = 0; xor_val < 64; xor_val++) {
                    for (int fl = 0; fl < 2; fl++) {
                        if (dp[v][xor_val][fl].cnt != -1) {
                            merge(dp[v + 1][xor_val][fl],
                                  dp[v][xor_val][fl].mx,
                                  dp[v][xor_val][fl].cnt);
                        }
                    }
                }
                continue;
            }

            // 组合数 C(c, 2)
            int c2 = (long long)c * (c - 1) / 2 % MOD;

            for (int xor_val = 0; xor_val < 64; xor_val++) {
                for (int fl = 0; fl < 2; fl++) {
                    if (dp[v][xor_val][fl].cnt == -1) continue;

                    int cur_mx = dp[v][xor_val][fl].mx;
                    int cur_cnt = dp[v][xor_val][fl].cnt;

                    // 1. 保留 0 个：移除全部 c 个
                    merge(dp[v + 1][xor_val][fl],
                          cur_mx + c,
                          mul(cur_cnt, 1));

                    // 2. 保留 1 个：移除 c-1 个
                    if (c >= 1) {
                        merge(dp[v + 1][xor_val ^ v][1],
                              cur_mx + c - 1,
                              mul(cur_cnt, c));
                    }

                    // 3. 保留 2 个：移除 c-2 个
                    if (c >= 2) {
                        merge(dp[v + 1][xor_val][1],
                              cur_mx + c - 2,
                              mul(cur_cnt, c2));
                    }
                }
            }
        }

        State ans = dp[max_val + 1][0][1];
        if (ans.cnt == -1) {
            cout << "-1\n";
        } else {
            cout << ans.mx << " " << ans.cnt << "\n";
        }
    }

    return 0;
}

验证样例

输入：

9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9

输出：

4 1
2 1
0 1
-1
8 2

与题目输出一致。

补充说明

• 代码中 c2 需要取模，因为后续要乘到方案数上。
• 注意 c2 的计算使用 (long long)c * (c - 1) / 2 % MOD 避免溢出。
• 由于 XOR 结果最大为 $63$（因为 $a_i \le 50$），所以 XOR 维大小取 $64$。
• 转移时，保留 $0$ 个的移除数增加 $c$，保留 $1$ 个增加 $c-1$，保留 $2$ 个增加 $c-2$。
• 方案数的乘法要用 mul 函数，加法用 add 函数，模 $998244353$。