题解归档 - cf2239F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239F
• 本地来源：problems/cf2239F/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/F
• 原始标题：CF2239F - Colorful Works

思路

CF2239F - Colorful Works

pattern

Burnside/Polya 看起来像本质不同树计数，但只要求模 2。关键是把每个点“每种颜色的孩子最多一个，且不能等于父边颜色”的递归写在 GF(2) 里。

claim

设 F_p(c) 为当前点的父边颜色是 p（根用无父边），每种颜色在后续路径还可用 c_i 次时，满足所有上界的 rooted colored tree 同构类数量的奇偶。

递归为

F_p(c)=prod_{i!=p,c_i>0}(1+F_i(c-e_i))。

在 GF(2) 中，F_p(c)=1 当且仅当所有可走后继都是 0。这正是一个游戏的必败态：每步选一个非父边颜色 i，把 c_i 减一，下一步不能再选 i。

带禁色 p 的完整判定：

F_p(c)=1 当且仅当下面至少一个成立：

• c_p >= sum_{i!=p} c_i，因为禁色颜色本身就是足够大的“后手储备”；
• sum c_i 为偶数，且 max c_i <= sum c_i - max c_i。

根状态没有禁色，所以只剩第二条：

F_root(c)=1 当且仅当 sum c_i 为偶数，且 max c_i <= sum c_i - max c_i。

证明思路是对上面的禁色判定做归纳：

• 若 c_p >= others，任意合法步只能取非 p，新状态既不会让新禁色成为储备，也会让 p 成为严格多数，所以后继全是必胜。
• 若总和偶数且无严格多数，任意合法步后总和变奇数，新禁色也不可能成为储备，所以后继全是必胜。
• 若两条都不成立：有严格多数时取那个严格多数颜色；否则总和为奇数，取一个非禁色的最大颜色（若最大是禁色，就取任意正的非禁色颜色）。后继满足第二条。

necessary / sufficient

下界 [l_i,r_i] 用 Möbius 异或处理。对每个颜色，上界端点只可能取：

• r_i
• 若 l_i>0，还要异或 l_i-1

因此答案是所有端点选择 x_i 中满足

sum x_i 为偶数且没有严格多数颜色

的选择数奇偶。

把每个颜色写成最小端点 a_i 加可选增量：

• 若 l_i=0，只有 a_i=r_i
• 若 l_i>0，a_i=l_i-1，可选增量 d_i=r_i-l_i+1

令 A=sum a_i。

总和偶数部分只需要 2 状态 parity DP。

严格多数部分唯一：如果颜色 i 的端点为 x，其它颜色端点和必须 <x 且同奇偶。其它颜色的可选增量用

Q(z)=prod(1+z^{d_i})

在 GF(2) 下截到最大可能查询值。若要排除颜色 i 自己的增量，查询

Q/(1+z^{d_i}) = Q*(1+z^{d_i}+z^{2d_i}+...)。

所以一次查询为

xor_{q>=0} prefix_Q(K-q*d, parity xor q*d parity)。

brute/check

• 上界递归对 n<=5, c_i<=4 与 sum even and max balanced 对拍通过。
• 区间答案对随机小数据用枚举所有端点选择与实现公式对拍通过。
• 样例通过。

edge

• l_i=0 没有第二个端点。
• mx<0 时没有严格多数查询，只剩总和偶数部分。
• d_i>mx 的因子在截断多项式中等于 1，排除它时商也等于原多项式。

Implementation note: 当前提交版只保留 a_i,d_i，用 d_i==0 表示原来 l_i=0 的单端点项；cnt 用 int 足够，pre 只存 0/1 用 char。q/qq 会 reserve，避免大测试首次扩容抖动。

代码

来源：problems/cf2239F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2000005;
int a[maxn],d[maxn];
struct node{
    int d,k,p;
};
vector<unsigned long long>bit;
vector<char>pre[2];
vector<int>cnt;
vector<node>q;
vector<pair<int,int>>qq;
int mx;
void addbit(int x){
    int i,w,o;
    unsigned long long v;
    w=x>>6;
    o=x&63;
    for(i=(int)bit.size()-1;i>=w;i--){
        v=bit[i-w]<<o;
        if(o and i-w-1>=0) v|=bit[i-w-1]>>(64-o);
        bit[i]^=v;
    }
}
int getbit(int x){
    return (bit[x>>6]>>(x&63))&1;
}
int ask(int d,int k,int p){
    int ans,cur;
    ans=0;
    cur=0;
    while(k>=0){
        ans^=pre[p^((cur&1)&(d&1))][k];
        cur++;
        k-=d;
    }
    return ans;
}
int main(){
    int t,n,i,zc,pd,ans,dp0,dp1,ndp0,ndp1,L,R;
    ll sum,now;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        sum=0;
        dp0=1;
        dp1=0;
        mx=-1;
        q.clear();
        qq.clear();
        q.reserve(2*n);
        qq.reserve(n);
        for(i=1;i<=n;i++){
            scanf("%d%d",&L,&R);
            if(L==0){
                a[i]=R;
                d[i]=0;
            }else{
                a[i]=L-1;
                d[i]=R-L+1;
                ndp0=dp0;
                ndp1=dp1;
                if(d[i]&1){
                    ndp0^=dp1;
                    ndp1^=dp0;
                }else{
                    ndp0^=dp0;
                    ndp1^=dp1;
                }
                dp0=ndp0;
                dp1=ndp1;
            }
            sum+=a[i];
        }
        ans=(sum&1)?dp1:dp0;
        for(i=1;i<=n;i++){
            if(d[i]){
                now=2LL*a[i]-sum-1;
                if(now>=0){
                    q.push_back({d[i],(int)now,(int)((now+1)&1)});
                    if(now>mx) mx=now;
                }
                now=2LL*a[i]+d[i]-sum-1;
                if(now>=0){
                    q.push_back({d[i],(int)now,(int)((now+1)&1)});
                    if(now>mx) mx=now;
                }
            }else{
                now=2LL*a[i]-sum-1;
                if(now>=0){
                    qq.push_back({(int)now,(int)((now+1)&1)});
                    if(now>mx) mx=now;
                }
            }
        }
        if(mx>=0){
            cnt.assign(mx+1,0);
            for(i=1;i<=n;i++){
                if(d[i] and d[i]<=mx) cnt[d[i]]++;
            }
            bit.assign((mx+64)/64,0);
            bit[0]=1;
            for(i=1;i<=mx;i++){
                if(cnt[i]&1) addbit(i);
                if(cnt[i]>=2 and i*2<=mx) cnt[i*2]+=cnt[i]/2;
            }
            pre[0].assign(mx+1,0);
            pre[1].assign(mx+1,0);
            zc=0;
            pd=0;
            for(i=0;i<=mx;i++){
                if(getbit(i)){
                    if(i&1) pd^=1;
                    else zc^=1;
                }
                pre[0][i]=zc;
                pre[1][i]=pd;
            }
            for(i=0;i<(int)qq.size();i++) ans^=pre[qq[i].second][qq[i].first];
            for(i=0;i<(int)q.size();i++) ans^=ask(q[i].d,q[i].k,q[i].p);
        }
        printf("%d\n",ans&1);
    }
    return 0;
}