题解：CF2056F2 Xor of Median (Hard Version)

chenbs · 2025-10-23 14:56:12 · 题解

引理

若 a 的二进制上 1 的位置集合是 b 的子集，则记作 a \subset b。所有变量都是整数。

引理 1：{n \choose m} 为奇数，当且仅当 m \subset n。

引理 2：{n \brace m} 为奇数，当且仅当 (n-m) \operatorname{and} \lfloor \frac{m-1}{2} \rfloor = 0。（\operatorname{and} 为按位与）。

引理 3：{n \choose {m_1, m_2, \dots m_p}} 为奇数，当前仅当 m_1, m_2, \dots m_p 是 n 的二进制划分。即 m_1 \operatorname{or} m_2 \operatorname{or} \dots \operatorname{or} m_p = n，m_i \operatorname{and} m_j = 0 (1\le i,j\le p)

引理 4：\bigoplus_{i=0}^{4x+y} i = \begin{cases} 4x, y=0 \\ 1, y=1 \\ 4k+3, y=2 \\ 0, y=3 \end{cases}

此处只证明引理 3。首先 {n \choose m_1} 要是奇数，所以 m_1 \subset n，然后 {n-m_1 \choose m_2} 也要是奇数，所以 n 去掉 m_1 的部分要包含 m_2。以此类推，n 就是 m_1, m_2, \dots m_p 的二进制划分。

F1 题解

首先，可以枚举 \text{cnt} 数组，考虑对答案的贡献。由引理 3，若一种 \text{cnt} 想对答案产生贡献，必须是 n 的二进制划分。此时最大的 \text{cnt} 一定超过总和的一半，所以中位数就是最大值。

记 n 中 1 的位置数为 b，枚举 \text{cnt} 数组不为零的位置数 p、原数组 a 的最大值 x，答案为：

这里简单解释一下，首先 b 个二进制位要分成 p 份后排序，这里的方案数就是第二类斯特林数，然后原数组要从 [0,x) 中选 p-1 种数（x 已经是最大值了）。

这样 F1 就做完了，使用引理 1、引理 2 计算，时间复杂度 O(km)。

#include<bits/stdc++.h>
using namespace std;
int t,k,n,m,ans;
char n2[200005];
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%s",&k,&m,n2);
        n=0;
        for(int i=0; i<k; i++) n+=(n2[i]=='1');
        ans=0;
        for(int y=1; y<=min(n,m); y++)
            for(int x=0; x<m; x++)
                if(((y-1)|x)==x && ((n-y)&((y-1)/2))==0)
                    ans^=x;
        printf("%d\n",ans);
    }
    return 0;
}

F2 题解

记：

答案就是 \bigoplus_{x=0}^{m-1} f(x) x。

我们分成两个部分进行优化，第一部分是计算 f(x)，第二部分是快速求异或和。

第一部分的可以使用 sosdp。

注意到 x 的高位均没有用。形式化地，令 N 是最小的满足 2^N > min(n,m) 的数，f(x) = f(x \bmod 2^N)。因此只需要处理 [0, 2^N) 部分的 f(x) 就行了，这一部分时间复杂度 O(k \log k)。

第二部分，由引理 4 可以简单计算。

#include<bits/stdc++.h>
using namespace std;
int t,k,n,m,N,ans;
char n2[200005];
int f[300005];
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%s",&k,&m,n2);
        n=0;
        for(int i=0; i<k; i++) n+=(n2[i]=='1');
        ans=0;
        int N=0;
        while((1<<N)<=min(n,m)) N++;
        for(int j=0; j<(1<<N); j++) f[j]=(j<n && j<m && (((n-j-1)&(j/2))==0));
        for(int i=0; i<N; i++)
            for(int j=0; j<(1<<N); j++)
                if(j&(1<<i))
                    f[j]^=f[j^(1<<i)];
        // 分块计算
        int t=0, cnt=0;
        for(int x=0; x<(1<<N); x++)
            if(f[x])
                t^=x, cnt++;
        int x=0, bk=m>>N;
        if(bk&1) ans^=t;
        if(cnt&1) {
            // 0 xor 1 xor 2 xor ... xor bk-1
            switch((bk-1)&3) {
                case 0: {
                    ans^=((bk-1)>>2<<2)<<N;
                    break;
                }
                case 1: {
                    ans^=1<<N;
                    break;
                }
                case 2: {
                    ans^=(((bk-1)>>2<<2)+3)<<N;
                    break;
                }
            }
        }
        for(int x=((m>>N)<<N); x<m; x++) ans^=x*f[x%(1<<N)];
        printf("%d\n",ans);
    }
    return 0;
}