夏晓光(loveJY)的博客

为什么要浪费一篇博文写这个啊?

因为他可是游戏人生啊!!!

先搞出每个点的sg值,sg值是其出边所有点sg值的mex,因为这个是拓扑图所以可行

然后考虑$f_i$表示开始sg值为i的到最后的胜利的概率

转移考虑枚举sg值为啥的点进行转移即可

$f_i=\sum p_{j->i} f_j+ \frac{1}{n+1}*[u!=0]$

因为这个是带环图,所以要高斯消元

而sg值向来都很小,这道题就算玩命构造因为状态数很少所以mex值还是很小,500级别

注意u=0时不能直接胜利哈,所以不乘$\frac{1}{n+1}$

哇哈高斯消元小心我们一定不要拿自己消除自己服了服了

然后还有特判0哦

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 4e5 + 7;
const int P = 998244353;
int n, m, ccnt, ccnt2, N;
int nxt[MAXN], to[MAXN], home[MAXN], mex[MAXN], sg[MAXN];
int nxt2[MAXN], to2[MAXN], home2[MAXN], out[MAXN], que[MAXN], xs[MAXN];
ll fac[MAXN], ifac[MAXN], inv[MAXN];
inline void ct2(int x, int y) {
	ccnt2++;
	nxt2[ccnt2] = home2[x];
	to2[ccnt2] = y;
	home2[x] = ccnt2;
}

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	to[ccnt] = y;
	home[x] = ccnt;
	out[y]++;
}

inline ll  ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init() {
	int hd = 1, tl = 0;
	memset(sg, -1, sizeof(sg));
	for(int i = 1; i <= n; ++i)if(out[i] == 0)que[++tl] = i, sg[i] = 0;
	while(hd <= tl) {
		int u = que[hd];
		++hd;
		// printf("%d ?\n", u);
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			out[v]--;
			if(!out[v])que[++tl] = v;
			// printf("%d ?\n", v);
		}
		if(sg[u] == -1) {
			// printf("%d %d?\n", u, home2[u]);
			for(int i = home2[u]; i; i = nxt2[i]) {
				int v = to2[i];
				// printf("%d->%d\n", u, v);
				mex[sg[v]] = u;
			}
			sg[u] = 0;
			while(mex[sg[u]] == u)sg[u]++;
		}
	}
	for(int i = 1; i <= n; ++i) {
		xs[sg[i]]++;
		// printf("%d ", sg[i]);
		N = max(N, sg[i]);
	}
	for(int i = 0;; ++i) {
		if((1 << i) > N) {
			N = (1 << i) - 1;
			break;
		}
	}
	// printf("%d?\n", N);
	fac[0] = 1;
	ifac[0] = 1;
	for(int i = 1; i <= n + 2; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[n + 2] = ksm(fac[n + 2], P - 2);
	for(int i = n + 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	for(int i = 1; i <= n + 2; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
	// printf("%lld %lld?\n", inv[2], inv[3]);
	return;
}
const int MAXM = 520;
ll a[MAXM][MAXM];

inline void guass() {
	for(int i = 0; i <= N; ++i) {
		int t = i;
		while(a[t][i] == 0)++t;
		if(t != i)
			for(int j = 0; j <= N + 1; ++j) {
				swap(a[i][j], a[t][j]);
			}
		ll kk = ksm(a[i][i], P - 2);
		// printf("%lld ?%lld\n", kk, a[i][i]);
		for(int j = 0; j <= N + 1; ++j) {
			a[i][j] = a[i][j] * kk % P;
		}
		for(int j = 0; j <= N; ++j) {
			if(i == j)continue;
			ll kk = a[j][i];
			for(int k = 0; k <= N + 1; ++k) {
				a[j][k] = (a[j][k] - kk * a[i][k] % P + P) % P;
			}
		}
		// for(int i = 0; i <= N + 1; ++i) {
		// 	for(int j = 0; j <= N + 1; ++j)
		// 		printf("%lld ", a[i][j]);
		// 	puts("");
		// }
	}
	return;
}

inline void solve() {
	for(int i = 0; i <= N; ++i) {
		for(int j = 0; j <= N; ++j) {
			a[i][j] = 1ll * xs[i ^ j] * inv[n + 1] % P;
			// printf("%d %d %d\n", i, j, xs[i ^ j]);
		}
		a[i][i] += P - 1;
		a[i][i] %= P;
		if(i != 0)a[i][N + 1] = inv[n + 1];//常数项
	}
	// for(int i = 0; i <= N + 1; ++i) {
	// 	for(int j = 0; j <= N + 1; ++j)
	// 		printf("%lld ", a[i][j]);
	// 	puts("");
	// }
	// puts("\n");
	guass();
	// for(int i = 0; i <= N + 1; ++i) {
	// 	for(int j = 0; j <= N + 1; ++j)
	// 		printf("%lld ", a[i][j]);
	// 	puts("");
	// }
	printf("%lld\n", (P - a[0][N + 1]) % P);
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		ct(y, x);
		ct2(x, y);
	}
	init();
	solve();
	return 0;
}