[Opoi 2025] CCD 的异或 II 题解

· · 题解

link

思路

对于 A_l 到 A_r 的异或和需要等于 1，我们可以转化为在前缀异或和 S 中，S_r\ne S_{l-1}。

考虑对 S_r\ne S_{l-1} 连无向边 (l-1,r)。如果合法，最终得到的图一定是若干个联通的二分图。

考虑反证。

假设最终得到的图不是二分图。因为不是二分图证明存在奇环，设该奇环的节点为 a_1,a_2,\dots,a_m，则须满足 S_{a_1}\ne S_{a_2},S_{a_2}\ne S_{a_3} ,\dots S_{a_{m-1}}\ne S_{a_m},S_{a_m}\ne S_{a_1}。由于 m 为奇数且 S\in\{0,1\}，所以 S_{a_1}=1,S_{a_2}=0,\dots,S_{a_m}=1 或 S_{a_1}=0,S_{a_2}=1,\dots,S_{a_m}=0，假设不成立，证毕。

然后就会产生若干个联通的二分图。考虑在每个二分图中，将一个节点设为 0 或 1，则会分别形成一种 S 的取值，每个联通的二分图就会有 2 种可能。

设联通的二分图的数量为 c，则第一问的答案为 2^{c-1}。为啥需要减一呢？因为 S_0 的值只能为 0，所以 0 所在的连通块就只有一种可能。

然后考虑第二问。因为 A_i=S_{i} \operatorname{xor} S_{i-1}，所以为了让字典序尽可能小，我们只需在判定二分图时，将 i 的染色变为 S_{i-1} 就行啦（这样就能让A_i=0，使字典序变小）。

Code

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10,M=2e6+10,P=998244353;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
int color[N];
bool dfs(int x,int c){
    color[x]=c;
    for(int i=h[x];~i;i=ne[i]){
        int y=e[i];
        if(color[y]==-1){
            if(!dfs(y,1-color[x]))return 0;
        }
        else if(color[y]==c)return 0;
    }
    return 1;
}
int main(){
    memset(h,-1,sizeof h);
    memset(color,-1,sizeof color);
    cin>>n>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        add(l-1,r),add(r,l-1);
    }
    int ans=1,res=0;
    for(int i=0;i<=n;i++){
        if(color[i]==-1){
            if(!dfs(i,color[i-1]))return cout<<0<<'\n',0;
            if(i)ans=ans*2%P;
        }
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
        cout<<(color[i-1]^color[i]);
    return 0;
}