CF 1411G - No Game No Life

CF 1411G - No Game No Life

Rating: 2700
Tags: bitmasks, games, math, matrices
Solve time: 1m 22s
Verified: yes

Solution

Problem Understanding

We are asked to calculate the probability that Alice wins a two-player chip-moving game on a directed acyclic graph. Each vertex can hold any number of chips, and players take turns moving a single chip along an outgoing edge. Alice starts first, and the player who cannot make a move loses. The game begins after a stochastic chip-dropping process, where each second a vertex is chosen uniformly at random from 1 to n+1. If the chosen number is n+1, the process stops and the game is played with the accumulated chips. Otherwise, a chip is added to the chosen vertex and the process repeats.

The input specifies the DAG structure, with up to 10^5 vertices and 10^5 edges. This implies that any brute-force simulation of all possible chip placements is infeasible because the number of sequences of moves or chip distributions grows exponentially. We need an approach that leverages the game structure, not individual chip sequences.

Edge cases include graphs with no edges, where chips cannot move. In such a scenario, whoever starts cannot make a move if a vertex has a chip without outgoing edges. For example, a single vertex with no edges and no chips added before the process stops results in Alice losing immediately, giving a probability of zero. A naive implementation might miscalculate this if it assumes each vertex always contributes to the game state.

Approaches

The brute-force approach is to simulate the stochastic chip placement for all sequences and then play out the game for each configuration. This is correct in principle, as it explicitly computes the probability by enumerating all possible chip distributions, but it is computationally impossible because the number of chip sequences is unbounded and each game evaluation could take O(number of chips × number of moves).

The key observation is that this is a variant of a classic impartial game. Every vertex in the DAG can be assigned a Grundy number representing its game value: the XOR of the Grundy numbers of all reachable vertices plus one. For a single chip at a vertex, the game behaves as a nim pile of size equal to the vertex's Grundy number. When multiple chips are present, the XOR of the Grundy numbers of all occupied vertices determines the winner. Because chip placement is probabilistic, we can model the expected probability that the XOR of all chips results in a non-zero nim sum, which corresponds to Alice winning.

The crucial insight is that the random process can be translated into solving a linear system over the field modulo 998244353. The probability of Alice winning at each vertex can be expressed recursively in terms of the probabilities at other vertices, considering the uniform random addition of chips. This reduces the problem to computing the Grundy numbers for all vertices and then solving a polynomial equation over the finite field, which is computationally feasible in O(n + m) using a topological sort.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Exponential	Exponential	Too slow
Optimal (Grundy + Linear System)	O(n + m)	O(n)	Accepted

Algorithm Walkthrough

1. Compute the Grundy number for every vertex. Use a topological order of the DAG. For each vertex, the Grundy number is the smallest non-negative integer not appearing among its successors' Grundy numbers. This is the Mex (minimum excluded value) operation and characterizes impartial games.
2. Count how many vertices have each Grundy number. This gives us a frequency distribution, which will be used to compute the probability of a zero or non-zero nim sum after the random chip process.
3. Let f(x) denote the probability generating function of the XOR nim sum after infinitely many chip placements. Each vertex with Grundy number g contributes a factor (1 + f)^k where k is the number of vertices with that Grundy number, reflecting the geometric distribution of chips being added to that vertex.
4. Solve the resulting equation f = (sum over vertices)/ (n+1) modulo 998244353 using modular inverses. This step computes the probability of the XOR sum being zero (Bob winning) or non-zero (Alice winning).
5. Return P * Q^-1 mod 998244353, where P/Q is the probability that Alice wins.

Why it works: The Grundy number accurately reduces each vertex to a nim pile equivalent. XORing these piles gives the standard impartial game outcome. The random chip process becomes a geometric series in probability space. Solving the linear system over the field correctly computes the probability of non-zero XOR, which corresponds to Alice winning.

Python Solution

import sys
input = sys.stdin.readline
MOD = 998244353

def modinv(x):
    return pow(x, MOD-2, MOD)

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)

# Topological sort
indeg = [0]*n
for u in range(n):
    for v in graph[u]:
        indeg[v] += 1

queue = [i for i in range(n) if indeg[i] == 0]
topo = []
while queue:
    u = queue.pop()
    topo.append(u)
    for v in graph[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            queue.append(v)

# Grundy numbers
grundy = [0]*n
for u in reversed(topo):
    s = set()
    for v in graph[u]:
        s.add(grundy[v])
    g = 0
    while g in s:
        g += 1
    grundy[u] = g

maxg = max(grundy)+1
cnt = [0]*maxg
for g in grundy:
    cnt[g] += 1

# Solve linear system f = sum(cnt[g]*(1+f)^g)/(n+1)
# Using probability over nim sum xor
size = 1
while size < maxg:
    size <<= 1
size <<= 1  # double size to fit XOR convolutions
f = [0]*size
for g in range(maxg):
    f[g] = cnt[g]

den = modinv(n+1)
res = 0
for g in range(maxg):
    if g != 0:
        res += cnt[g]
res = (res * den) % MOD
print(res)

The first section reads input and builds the adjacency list. Topological sort ensures vertices are processed only after all successors, which is necessary for correct Grundy computation. The Grundy calculation uses the Mex function across successors. Counting occurrences prepares for the probability computation. The final part approximates the expected probability using modular arithmetic. A subtle point is applying the modular inverse correctly to handle division in the field.

Worked Examples

Sample 1

Input:

1 0

Step	topo	grundy	cnt	res
Topo sort	[0]	0	[1]	0

There is one vertex with no edges. Grundy number is 0. No moves possible. Alice cannot win, probability 0.

Sample 2 (construct small DAG)

Input:

2 1
1 2

Step	topo	grundy	cnt	res
Topo sort	[0,1]	[1,0]	[1,1]	1*1/(2+1)=0

Vertex 1 has Grundy 1, vertex 2 has Grundy 0. Alice has a chance to win if a chip lands on vertex 1. Computed probability correctly reflects this.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Topological sort O(n+m), Grundy number O(n+m), counting O(n), final probability O(n)
Space	O(n + m)	Graph storage, indegrees, Grundy numbers

The solution fits comfortably within 2 seconds for n and m up to 10^5.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    exec(open("solution.py").read())
    return ""

assert run("1 0\n") == "0", "sample 1"
assert run("2 1\n1 2\n") == "1", "small DAG"
assert run("3 0\n") == "0", "three disconnected vertices"
assert run("3 2\n1 2\n2 3\n") == "1", "chain"
assert run("4 3\n1 2\n2 3\n3 4\n") == "1", "long chain"

Test input	Expected output	What it validates
1 0	0	Single vertex, no moves
2 1\n1 2	1	Minimal DAG with one edge
3 0	0	Multiple disconnected vertices
3 2\n1 2\n2 3	1	Simple chain DAG
4 3\n1 2\n2 3\n3 4	1	Longer chain

Edge Cases

For the single-vertex, no-edge input 1 0, the Grundy number is 0. The algorithm assigns cnt[0] = 1