题解 ARC156D 【Xor Sum 5】

Sol1 · 2023-07-08 09:06:23 · 题解

给个简单做法，不用 Lucas 定理，不用生成函数！

考虑到异或满足相同抵消为 0，这是一个和模 2 计数相似的性质，提示我们寻找双射。

不难发现对于一个序列 (X_1,X_2,\cdots,X_K)，如果它不是一个回文序列，则可以直接将其双射到它反过来的序列 (X_K,X_{K-1},\cdots,X_1)，两者的 \sum A_{X_i} 显然是一样的，于是相互抵消。

于是我们只需要对回文的 X 序列求 \sum A_{X_i} 的异或和即可。

此时，如果 K 是偶数，则将序列从中间折半，必有前后两半的 \sum A_{X_i} 相等。于是可以直接将 K 除以 2 之后递归做。具体来说，设 f_i 为 K=i 时的答案，则我们有 f_{2i}=2f_{i}。

然而如果 K 是奇数就不能直接折半了，因为最后整体的和要加上中间的一项。

于是一个很自然的想法就是把整体加的这一项记下来。发现这样就可以完成所有计算：

• 对于 K 是奇数的情况，可以直接枚举中间的项是什么，然后把它加到整体加的项里面，即可转化为 K 是偶数的情况。
• 对于 K 是偶数的情况，最后一位的值只和整体加的量，以及折半以后可能的序列个数有关。前者已经被记录，后者只和 N\bmod 2 有关，于是可以计算出最后一位；剩下的位就是折半后整体加当前的整体加的量的二分之一下取整的值。（这一部分可以结合下面的转移式理解）

于是我们就得到了最终的做法：

设 f(i,j) 表示：对所有长度为 i 的序列 (X_1,X_2,\cdots,X_i)，j+\sum_{k=1}^i A_{X_k} 的异或和。

对于偶数 i=2x，有：

对于奇数 i=2x+1，有：

边界状态：

目标状态为 f(K,0)。

归纳易证第二维的最大值就是序列 A 的最大值，而第一维显然只有 \log K 个。转移再乘上一个 N，总复杂度即为 O(N\log K\cdot \max A)。

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

int n, a[1005];
long long k, dp[77][1005];
bool vis[77][1005];

inline void Read() {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> a[i];
}

inline long long Dfs(int dep, int pls) {
    if (vis[dep][pls]) return dp[dep][pls];
    if ((k >> dep) == 1) {
        vis[dep][pls] = 1;
        for (int i = 1;i <= n;i++) dp[dep][pls] ^= (a[i] + pls);
        return dp[dep][pls];
    }
    vis[dep][pls] = 1;
    if (!((k >> dep) & 1)) return dp[dep][pls] = (Dfs(dep + 1, pls >> 1) << 1) | ((pls & 1) && (n & 1));
    else {
        dp[dep][pls] = 0;
        for (int i = 1;i <= n;i++) dp[dep][pls] ^= (Dfs(dep + 1, (pls + a[i]) >> 1) << 1) | (((pls + a[i]) & 1) && (n & 1));
        return dp[dep][pls];
    }
}

int main() {
    Read();
    cout << Dfs(0, 0) << endl;
    return 0;
}