CF1149E Election Promises 题解

题意：

给定一张 \(n\) 个点 \(m\) 条边的有向图（不一定连通），每个点有一个权值 \(a_i\) 。

两人轮流进行操作，每次操作可以选择任意一个节点 \(u\) 并将其点权减小为一个非负整数，

之后可以将所有节点 \(v \in\{v \mid (u,v) \in E\}\) 的权值更改为任意非负整数

最先不能操作者输（指减小 \(u\) 的操作），求先手有无必胜策略。

若有必胜策略则接下来输出第一次操作后能够确保获胜的每个节点的权值

数据范围：

\(1 \leq n \leq 2 \times 10^5, 0 \leq m \leq 2 \times 10^5,~0 \le a_i \le 2\times 10^{18}\) 。

可以发现，如果这张图全是单点，即出度全为 \(0\) 时，这就是一个 Nim 游戏。

考虑对每个点进行如下分组：

出度为 \(0\) 的点标号为 \(0\) 。
对原图拓扑排序，每个点的标号是它后继节点的 \(\operatorname{mex}\) 。

这样分组显然有以下性质

对于任意有向边 \((u,v) \in E\) ，\(u,v\) 必定不在一个组内。
如果记点 \(i\) 的编号为 \(\mathrm{id}(i)\) ，那么 \(i\) 的后继节点中至少有一个在 \([0,\mathrm{id}(i))\) 中。

提示：其实这种分组方式是在计算 \(\rm SG\) 函数，于是我们用 \(\rm SG\) 来替代 \(\mathrm{id}\) 表示编号。

考虑记 \(f_i = \bigoplus_{\mathrm{SG}(p)=i}a_p\) ，即编号为 \(i\) 的所有点的异或值。

那么可以证明，当且仅当 \(\forall\, i\) 有 \(f_i = 0\) 时，先手必败，否则先手必胜。

证明考虑证明采取以上策略时，原问题转化为一个有向图游戏。

记先手必胜态为 \(\rm N\) ，先手必败态为 \(\rm P\) 。有向图游戏满足性质：

终止状态为 \(\rm P\) 。

\(\rm P\) 的后继均为 \(\rm N\) 。

\(\rm N\) 的后继存在至少一个 \(\rm P\) 。

那么我们只需证明双方均采取最优策略时，满足以上性质即可：

本题的终止状态即所有的为 \(0\) 的状态，显然为 \(\rm P\) 。

对于 \(\rm P\) 态，即 \(\forall i,f_i=0\) 时，任何修改都会使得某个位置 \(x\) 满足 \(f_x \ne 0\) ，显然后继只有 \(\rm N\) 态。

对于 \(\rm N\) 态，至少存在一个位置 \(x\) 满足 \(f_x \ne 0\) 。

类似于 Nim 游戏，我们只需要找到最大的 \(x\) ，并找到一个 \(u\) ，使得 \[ \mathrm{SG}(u)=x,\ a_u \oplus f_x < a_u \] 然后令 \(a_u \gets a_u \oplus f_x\) 即可将 \(f_x\) 清零。那么这样的 \(u\) 一定存在吗？

设 \(f_x=k\) ，它的二进制下最高位的 \(1\) 为 \(2^d\) ，根据异或的定义，

一定有奇数个 \(\mathrm{SG}(p)=x\) 的 \(a_p\) 在二进制下第 \(d\) 位为 \(1\) ，因此一定存在这样的 \(u\) 。

而对于其他的 \(f_y \ne 0(y < x)\) ，由于 \(\rm SG\) 值由 \(\rm mex\) 得到，那么 \(u\) 的后继中一定存在 \[ v \in \{v \mid \mathrm{SG}(v)=y\, \land\,f_y \ne0\, \land\, y < x\} \]

因此只需要将 \(a_v \gets a_v \oplus f_y\) 即可。那么 \(\rm N\) 态下必然存在后继 \(\rm P\) 。\(\square\)

题目只需要给出先手操作一次后的状态，于是我们按照最优策略做即可。

时间复杂度 \(\mathcal{O}(n\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(2e5 + 15))

map<int,char> mp[N];
vector<int> vec[N], vec2[N];
int mx, a[N], in[N], SG[N], XOR[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) { static int u, v; cin >> u >> v; vec[v].pb(u); ++in[u]; vec2[u].pb(v); }
    static queue<int> q; rep(i, 1, n) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = 0; true; i++) if(!mp[u][i]) { SG[u] = i; break; }
        for(int v : vec[u]) { mp[v][SG[u]] = true; if(!(--in[v])) q.push(v); }
    }
    rep(i, 1, n) { XOR[SG[i]] ^= a[i]; up(mx, SG[i]); }
    Rep(i, mx, 0)
    {
        if(XOR[i])
        {
            rep(j, 1, n) if(SG[j] == i && (a[j] ^ XOR[i]) < a[j])
            {
                a[j] ^= XOR[i]; XOR[i] = 0;
                for(int v : vec2[j]) if(XOR[SG[v]]) { a[v] ^= XOR[SG[v]]; XOR[SG[v]] = 0; } break;
            }
            cout << "WIN\n"; rep(l, 1, n) cout << a[l] << " \n"[l == n]; return 0;
        }
        if(i == 0) return cout << "LOSE\n", 0;
    }
    return 0;
}