CF 167E

裸的LGV Lemma

CODE

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 605;
const int MAXM = 100005;
int n, m, mod, in[MAXN], out[MAXN], d[MAXN], fir[MAXN], to[MAXM], nxt[MAXM], cnt;
inline void Add(int u, int v) { to[++cnt] = v, nxt[cnt] = fir[u], fir[u] = cnt, ++d[v]; }
int topo[MAXN], id[MAXN], cur, q[MAXN], s, t;
int f[MAXN][MAXN], a[MAXN][MAXN];
int S[MAXN], T[MAXN], cnts, cntt;
inline void kill(int a, int b, int &ii, int &ik, int &ki, int &kk, int &sign) {
    ii = 1, ik = 0;
    ki = 0, kk = 1;
    sign = 1;
    while(b) {
        (ii -= a/b * ki) %= mod;
        (ik -= a/b * kk) %= mod;
        a -= a/b * b;
        swap(a, b);
        swap(ii, ki);
        swap(ik, kk);
        sign = -sign;
    }
}
inline int Gauss(int N) {
    int ans = 1, ii, ik, ki, kk, sign;
    for(int i = 1; i <= N; ++i) {
        for(int k = i+1; k <= N; ++k) if(a[k][i]) {
            kill(a[i][i], a[k][i], ii, ik, ki, kk, sign);
            ans *= sign;
            for(int j = i; j <= N; ++j) {
                int _aij = (1ll * a[i][j] * ii + 1ll * a[k][j] * ik) % mod;
                int _akj = (1ll * a[i][j] * ki + 1ll * a[k][j] * kk) % mod;
                a[i][j] = _aij, a[k][j] = _akj;
            }
        }
        ans = 1ll * ans * a[i][i] % mod;
    }
    return ans;
}
int main ()
{
	scanf("%d%d%d", &n, &m, &mod);
	for(int i = 1, x, y; i <= m; ++i)
		scanf("%d%d", &x, &y), Add(x, y), ++in[y], ++out[x];
	for(int i = 1; i <= n; ++i) {
        if(!in[i]) S[++cnts] = i;
        if(!out[i]) T[++cntt] = i;
	}
	for(int i = 1; i <= n; ++i) if(!d[i]) q[t++] = i;
	while(s < t) {
		int u = q[s++]; id[topo[u] = ++cur] = u;
		for(int i = fir[u]; i; i = nxt[i])
			if(--d[to[i]] == 0) q[t++] = to[i];
	}
	for(int i = 1, u; i <= n; ++i) {
		u = id[i]; f[u][u] = 1;
		for(int j = i, v; j <= n; ++j) {
			v = id[j];
			for(int k = fir[v]; k; k = nxt[k]) (f[u][to[k]] += f[u][v]) %= mod;
		}
	}
	int N = cnts;
	for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            a[i][j] = f[S[i]][T[j]];
	printf("%d
", (Gauss(N)+mod)%mod);
}