QOJ7413 [300iq Contest 2] Determinant 题解

First Post:

Last Update:

感觉最后一步并不是不可触及，只是思维有所局限罢了。

该题要我们求一个邻接矩阵的行列式，直接求肯定不行，不妨将行列式写出来看看组合意义： 事实上，只有所有的 到 都有边时，这个排列 才对答案有贡献，而 形成了若干个环，也就是说，这个排列对应原图的一个环覆盖。而对于一个奇环，其对应的置换为偶置换，反之亦然。所以这个环覆盖的权值为 ，其中 为偶环个数。

在看原题面的限制，明示我们边双大小不超过 ，那么我们考察把所有边双连通分量缩起来后形成的那棵树，在树上 DP。

这时就有个错误的想法是把所有边双的行列式乘起来作为答案，它错就错在一条无向边也可以被作为一个偶环。

所以我们可以设 表示分量 对应子树， 到 那条边是否单独成环的答案。但是编转移时就会发现此时分量 中的每个点都有”被删“或者”不被删“两种选择，如果暴力枚举肯定是没前途的，只能做到有关 的指数复杂度。

注意到在 DP 时，分量内的覆盖方案都是通过求行列式来解决的，这启发我们把”被删“和”不被删“的选择纳入到图中，具体地，对原来每个点 建立一个虚点 ，设 为与 相连的所有儿子分量 的 之积，设 为 ，分别表示与 被删或不被删的贡献系数。那么连边 ，权值为 。连边 ，权值 ，连边 ，权值 。然后 与 之间按照原图连接。对这张新图求行列式就可以得到 ， 在删掉两个点后也容易求得。

于是本题就做完了，因为对每个大小为 的块需要 的复杂度，总时间复杂度为 。

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
119
120
121
const int N = 3e4 + 5,M = 1e6 + 5,K = 75,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) { if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int n,m,k;
int fir[N],nxt[M],to[M],ect = 1;
int dfn[N],low[N],cut[M],dfstime; // 把每个边双提出来
int e[K][K];
inline void addedge(int u1,int v1) {
	nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;
}
inline int Det(int num) {
	static int A[K][K];
	for(int i = 1;i <= num;i++)
		for(int j = 1;j <= num;j++)
			A[i][j] = e[i][j];
	int ans = 1;
	for(int i = 1;i <= num;i++) {
		if(!A[i][i])
			for(int j = i + 1;j <= num;j++)
				if(A[j][i]) {
					for(int k = 1;k <= num;k++) swap(A[i][k],A[j][k]);
					ans = P - ans;break;
				}
		if(!A[i][i]) return 0;
		ans = 1ll * ans * A[i][i] % P;
		int inve = qpow(A[i][i],P - 2);
		for(int j = 1;j <= num;j++)
			if(j != i) {
				int div = 1ll * A[j][i] * inve % P;
				for(int k = i;k <= num;k++) Plus(A[j][k],P - 1ll * div * A[i][k] % P);
			}
	}
	return ans;
}
void tarjan(int x,int from) {
	dfn[x] = low[x] = ++dfstime;
	for(int i = fir[x],y;y = to[i],i;i = nxt[i]) 
		if(y != from) {
			if(!dfn[y]) {
				tarjan(y,x);
				low[x] = min(low[x],low[y]);
				if(low[y] > dfn[x]) cut[i] = cut[i ^ 1] = true;
			}
			else low[x] = min(low[x],dfn[y]);
		}
}
int co[N],dp[N][2];
vector<int> vs[N];
void dfs0(int x,int col) {
	co[x] = col;vs[col].push_back(x);
	for(int i = fir[x],y;y = to[i],i;i = nxt[i])
		if(!co[y] && !cut[i]) dfs0(y,col);
}
int pre[N],suf[N];
int e2[K][K];
int c0[N];
void DP(int x,int fa) {
	int num = 2 * vs[x].size();
	int cnt = vs[x].size();
	for(int i = 0;i < cnt;i++)
		for(int t = fir[vs[x][i]],v;v = to[t],t;t = nxt[t])
			if(co[v] != fa && co[v] != x) DP(co[v],x);
	for(int i = 1;i <= num;i++) for(int j = 1;j <= num;j++) e[i][j] = 0;
	for(int i = 0;i < vs[x].size();i++)
		for(int t = fir[vs[x][i]],j;j = to[t],t;t = nxt[t]) {
			auto pp = std::find(vs[x].begin(),vs[x].end(),j);
			if(pp != vs[x].end()) e[i + 1][pp - vs[x].begin() + 1]++;
	}
	for(int i = 0;i < vs[x].size();i++) {
		int u = vs[x][i];
		int s0 = 1,s1 = 0;
		vector<int> son;son.push_back(0);
		for(int t = fir[u],v;v = to[t],t;t = nxt[t]) {
			if(co[v] == fa || co[v] == x) continue;
			son.push_back(co[v]);
			s0 = 1ll * s0 * dp[co[v]][0] % P;
		}
		pre[0] = 1;
		for(int i = 1;i < son.size();i++)
			pre[i] = 1ll * pre[i - 1] * dp[son[i]][0] % P;
		suf[(int)son.size()] = 1;
		for(int i = (int)son.size() - 1;i >= 1;i--)
			suf[i] = 1ll * suf[i + 1] * dp[son[i]][0] % P;
		for(int i = 1;i < son.size();i++)
			Plus(s1,1ll * dp[son[i]][1] * pre[i - 1] % P * suf[i + 1] % P);
		int p1 = i + 1,p2 = i + vs[x].size() + 1;
		e[p2][p2] = s0;
		e[p1][p2] = s1;e[p2][p1] = 1;
		c0[u] = s0;
	}
	dp[x][0] = Det(num);
	int psf = -1;
	for(int i = 0;i < cnt;i++)
		for(int t = fir[vs[x][i]],j;j = to[t],t;t = nxt[t])
			if(co[j] == fa) { psf = i + 1;break;}
	for(int i = 1;i <= num;i++)
		if(i != psf && i != psf + cnt)
		for(int j = 1;j <= num;j++) 
			if(j != psf && j != psf + cnt) {
			int p1 = i - (i >= psf) - (i >= psf + cnt);
			int p2 = j - (j >= psf) - (j >= psf + cnt);
			e2[p1][p2] = e[i][j];
		}
	num -= 2;
	for(int i = 1;i <= num;i++) for(int j = 1;j <= num;j++) e[i][j] = e2[i][j];
	dp[x][1] = 1ll * Det(num) * (psf > 0 ? c0[vs[x][psf - 1]] : 1) % P;
}
int main() {
	read(n);read(m);read(k);
	for(int i = 1;i <= m;i++) {
		int u,v;
		read(u);read(v);
		addedge(u,v);addedge(v,u);
	}
	tarjan(1,0);
	int col = 0;
	for(int i = 1;i <= n;i++) if(!co[i]) ++col,dfs0(i,col);
	DP(1,0);
	cout << dp[1][0] << endl;
	return 0;
}
≡