题解：CF1149E Election Promises

· · Solution

经典的，考虑求出 DAG 上每个点的 SG 函数 f_u：

  1. 令出度为 0 的点 f_u=0。
  2. 对于出度不为 0 的点 f_u={\rm mex}_{u\to v} f_v。

经典的，考虑构造一个刻画局面的函数 H(G)，满足：

  1. 对于终止局面，H(G)=0，先手必败。
  2. 对于任意 H(G)=0 的局面，任意操作后 H(G')\neq 0。
  3. 对于任意 H(G)\neq 0 的局面，存在一个操作使 H(G')=0。

神秘的，构造出 H(G)=\sum g(x)，其中 g(x)=\bigoplus\limits_{f_u=x} w_u。

证明：

  1. 任意 H(G)=0 的局面，任意操作后 H(G')\neq 0。
    • 由 f_u 的定义可知，\forall u\to v,f_u\neq f_v。
    • 若操作 u，g(f_u) 中只有 w_u 改变，故一定不为 0，则 H(G')\neq 0。
  2. 任意 H(G)\neq 0 的局面，存在一个操作使 H(G')=0。
    • 由 f_u 的定义可知，\forall x<f_u,\exist u\to v,f_v=x。
    • 这意味着我们可以 同时改变 g(x) 的一个前缀的值。
    • 找到最大的 g(x)\neq 0 的 x，记 g(x) 的最高位为第 k 位。
    • 找到一个第 k 位为 1 的 w_u（必定存在），显然 g(x)\oplus w_u<w_u。
    • 令 w_u=g(x)\oplus w_u，其他 g(x)\neq 0 的直接改 u 的出点即可。
    • 这样操作后，\forall x,g'(x)=0 即 H(G')=0。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define REPG(i,g,x) for(int i=g.head[x];~i;i=g.edge[i].nxt)
#define LL long long

template<class T>
inline void read(T &x){
    T s=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) s=s*10+c-'0';
    x=s*f;
}

const int N=2e5+5;
vector<int> E[N];
int n,m;int w[N];
int f[N],g[N];bool vf[N];
vector<int> G[N];

map<int,bool> mp; 
inline void dfs(int u){
    if(vf[u]) return ;
    f[u]=0;vf[u]=1;
    if(!E[u].size()) return ;
    for(auto v:E[u]) dfs(v);
    mp.clear();
    for(auto v:E[u]) mp[f[v]]=1;
    while(mp[f[u]]) f[u]++;
}

int main(){
    read(n),read(m);
    rep(i,1,n) read(w[i]);
    rep(i,1,m) {
        int u,v;read(u),read(v);
        E[u].push_back(v);
    }
    rep(i,1,n) E[0].push_back(i);
    dfs(0);
    rep(i,1,n) g[f[i]]^=w[i],G[f[i]].push_back(i);
    per(i,n,0){
        if(g[i]==0) continue;
        printf("WIN\n");
        int bit=30;
        while(!(g[i]&(1<<bit))) bit--;
        for(auto u:G[i]){
            if(!(w[u]&(1<<bit))) continue;
            w[u]=g[i]^w[u];g[i]=0;
            for(auto v:E[u]){
                if(!g[f[v]])continue;
                w[v]=g[f[v]]^w[v];
                g[f[v]]=0;
            }
        }
        rep(i,1,n) printf("%d ",w[i]);printf("\n");
        return 0;
    }
    printf("LOSE\n");
    return 0;
}