「CF1411G」No Game No Life

发表于 分类于

$Link$

有一个 $n$ 个点 $m$ 条边的有向无环图，每次不断在 $[1,n+1]$ 内随机一个整数 $x$，如果 $x\le n$，就在点 $x$ 上放一个石子，否则停止放石子。

之后，两人在这个图上玩组合游戏，每次选择一个石子向出边移动到下一个点，不能移动者就输了。

问先手赢的概率，对 $99824353$ 取模。

$1\le n\le10^5,0\le m\le10^5$。

首先把每个点的 $sg$ 函数值求出来，根据 $sg$ 定理可以得到：所有石子的 $sg$ 值异或起来 $=0$ 时，先手必胜。

注意到如果 $sg=x$，意味着 $0\sim x-1$ 都已经出现过。

设 $g_x$ 表示如果出现 $sg=x$ 的点，至少需要几条边，显然 $g_x=\frac{x(x+1)}{2}$，因此 $sg$ 值不超过 $\sqrt{m}$，也即最终所有的 $sg$ 值异或起来不超过 $512$。

设 $f_x$ 表示所有的 $sg$ 值异或的值为 $x$ 的概率，$cnt_x$ 为 $sg$ 值为 $x$ 的点的个数。我们有：
$$
f_x=\frac{1}{n+1}\sum_{i=0}^{511}f_i\times cnt_{x\oplus i}\
\sum_{i=0}^{511}f_i=1
$$
$512$ 个未知数，$512$ 个方程，直接高斯消元即可。

时间复杂度 $O(512n+512^3)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;
const int mod = 998244353;

int n, m;
struct Edge {
    int to, next;
} edge[N + 1];
int start[N + 1], tot, d[N + 1];
int sg[N + 1], app[N + 1][600];
int w[600];
namespace gause
{
int mat[601][601], f[601];
inline int pow(int x, int y)
{
    int ans = 1;

    while (y) {
        if (y & 1)
            ans = 1ll * ans * x % mod;
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return ans;
}
inline void solve()
{
    for (int i = 0; i <= 599; i++) {
        for (int j = i + 1; j <= 599; j++) {
            if (!mat[j][i])
                continue;
            int div = 1ll * mat[j][i] * pow(mat[i][i], mod - 2) % mod;
            for (int k = i + 1; k <= 600; k++)
                mat[j][k] = (mat[j][k] - 1ll * mat[i][k] * div % mod + mod) % mod;
        }
    }
    for (int i = 599; i >= 0; i--) {
        f[i] = mat[i][600];
        for (int j = i + 1; j <= 599; j++)
            f[i] = (f[i] - 1ll * mat[i][j] * f[j] % mod + mod) % mod;
        f[i] = 1ll * f[i] * pow(mat[i][i], mod - 2) % mod;
    }
    return;
}
}


inline void addedge(int u, int v)
{
    edge[++tot] = { v, start[u] };
    start[u] = tot;
    d[v]++;
    return;
}
inline void dfs(int u)
{
    if (sg[u] != -1)
        return;
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        dfs(v);
        app[u][sg[v]] = 1;
    }
    for (int i = 0; i < 600; i++) {
        if (!app[u][i]) {
            sg[u] = i;
            break;
        }
    }
    w[sg[u]]++;
    return;
}
int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        addedge(u, v);
    }
    memset(sg, -1, 4 * (N + 1));

    for (int i = 1; i <= n; i++)
        if (!d[i])
            dfs(i);
    for (int i = 0; i <= 600; i++)
        gause::mat[0][i] = 1;
    for (int i = 1; i <= 599; i++) {
        gause::mat[i][i] = (-n - 1 + mod) % mod;
        for (int j = 0; j <= 599; j++)
            gause::mat[i][j] = (gause::mat[i][j] + w[i ^ j]) % mod;
    }
    gause::solve();

    printf("%d\n", (1 - gause::f[0] + mod) % mod);
    return 0;
}