题目链接：https://qoj.ac/contest/280/problem/4686

题目大意：给每个点染色，问有多少种染色数满足存在一种染色方案使得：

  1. 每个颜色至少被染了一次，每个点都被染了一种颜色。
  2. 任意一个简单环上每种颜色的数量一样。
做法

注意到一个事情，两个环像个 $8$ 一样的相交，那么中间的那条路径也满足每种颜色的数量一样。

这启示我们或许可以把第二条当成方程一样，解一下方程。想到方程就想到了向量空间。虽然这一步是队长想的，并不是我想的，也许这并不自然

设一个 $n$ 维的向量空间，定义其中一个子空间 $S$ 满足：

其为 $span\{L_i\}$ ，其中 $L_i$ 为第 $i$ 个环所生成的向量，即 $L_{i,x}=1$ 当且仅当 $x$ 在环上，否则为 $0$ 。

可以看到，对于任意一个合法的染色方案：元素 $(a_1,a_2,….,a_n)\in S$ 满足每种颜色的加权和相等，其中加权和表示如果 $x$ 染色某种颜色，其对这个颜色的贡献为 $a_x$ 。

由于我们实际上只是用方程多生成了一些线性无关的方程，所以这与前面第二条是相互充要的，即一个方案是合法的当且仅当其在 $S$ 内任意一个元素下的颜色加权和相等。

这意外着如果我们能找到 $S$ 的另外一组基，就可以把问题变成求这组基下的合法染色方案。

不妨猜基中每个分量要么 $0$ 要么 $1$ ，且每个分量最多在一个元素中不为 $0$，由此可以发现，两个分量在一个元素中同时为 $1$ 等价于这两个元素在任何方程中的值都相等且存在一个方程中，其系数不为 $0$ 。

因此基实际上可以等价的看成，把每条边按照其所在的环的集合作为标准划分等价类（空集的点扔掉）。

而这又可以等价于按照其所在的 DFS 环的集合作为标准划分等价类（DFS 环指的是做一遍 DFS 后，由恰好一条非树边构成的环），原因是根据异或路径那个结论，每个环都可以当成若干个 DFS 环在异或意义下的线性表示，所以 DFS 环划分的等价类和所有环划分的等价类是一样的。

这样的话题目就好做了，答案就是每条链的长度的最大公约数，就做完了。

时间复杂度：$O(nm)$ 。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int gcd(int x, int y){return !x ? y : gcd(y % x, x);}
struct node{
	int y, next;
}a[N * 2]; int len = 1, las[N];
void ins(int x, int y){a[++len] = {y, las[x]}; las[x] = len;}
int col[N], tmp[N], fa[N];
bool v[N];
int rk[N][2], cnt;
int dfn[N], ti;
int n, m;
void add(vector<int> x){
	memset(v, 0, sizeof(v));
	swap(col, tmp);
	memset(rk, 0, sizeof(rk));
	rk[1][0] = cnt = 1;
	for(auto y : x) v[y] = 1;
	for(int i = 1; i <= m; i++){
		if(!rk[tmp[i]][v[i]]) rk[tmp[i]][v[i]] = ++cnt;
		col[i] = rk[tmp[i]][v[i]];
	}
}
void dfs(int x){
	dfn[x] = ++ti;
	for(int k = las[x]; k; k = a[k].next){
		int y = a[k].y;
		if(!dfn[y]){
			fa[y] = k ^ 1;
			dfs(y);
		}
		else if(dfn[y] < dfn[x] && k != fa[x]){
			vector<int> now;
			now.push_back(k / 2);
			int z = x;
			while(z != y){
				now.push_back(fa[z] / 2);
				z = a[fa[z]].y;
			}
			add(now);
		}
	}
}
int sum[N];
int main(){
	cin >> n >> m;
	cnt = 1;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		ins(x, y);
		ins(y, x);
		col[i] = 1;
	}
	for(int i = 1; i <= n; i++){
		if(!dfn[i]) dfs(i);
	}
	for(int i = 1; i <= m; i++){
		sum[col[i]]++;
	}
	int d = 0;
	for(int i = 2; i <= cnt; i++){
		d = gcd(d, sum[i]);
	}
	for(int i = 1; i <= m; i++){
		if(d % i == 0){
			cout << i << " ";
		}
	}
	cout << "\n";
	return 0;
}

但是怎么证明呢？

证明

首先，一个容易犯的误区是：等价类可以用 DFS 环划分，但是不代表 $S$ 就是可以只有 DFS 环所构成的元素生成。因为我当时犯了这个错误

所以问题关键就是如何利用所有环进行线性组合，组合出那组基来。（显然 $S$ 是那组基的子空间，现在只要证明这组基能够被生成就行了）

设每个环都是异或意义下 DFS 环的线性组合（这是唯一的，我之前另外一篇博客有介绍）：$L=\{L_{x_1}\oplus L_{x_2}…\oplus L_{x_{k}}\}$ ，而 $L$ 的方程也是由 $L_{x_1},…,L_{x_{k}}$ 的方程异或出来的。

设 $L_y\notin L$ ，考察环 $\{L_y\}\cup L$ ，可以发现，就是对 $L_{y}$ 中的所有元素取个反，设 $f(L)$ 表示 $L$ 代表的元素。

考察 $f(\{L_y\}\cup L)-f(L)$ ，可以得到其在 $L_y$ 上的每个点的分量是 $±2$ 。

现在证明，每个基都可以求出来。

对于等价类 $L=\{L_1,L_2,…,L_k\}$ ，假设其补集为 $L’=\{L’_1,L’_2,…,L’_t\}$ ，那么我们这么计算：

这个值是多少呢？

假设对于一个点 $x$，其的等价类 $\cap L’≠\emptyset$ （设交集为 $A$），那么其的系数可以用下面这个式子证明为 $0$ ：

$f(S\cup a)+f(S)$ 在 $x$ 处的分量为 $0$，其中 $a\notin S$ ，即可证明。

假设为 $\emptyset$ ，但是等价类为 $L$ 的一个真子集，假设 $a\in L$ 不在里面。

那么有 $f(S\cup a)-f(S)$ 在 $x$ 处的分量为 $0$，其中 $a\notin S$ ，即可证明。

可以证明，等价类在恰好等于 $L\cup L_1$ 的点的分量为 $±2^{|L|+|L’|}≠ 0$ ，其中正负号一致。

证毕。

高中的时候，我知道了那个异或环的性质，但是不会证明，然后在今年会证了，这个结论在去年知道了，今年也会证了，感叹时光的流逝，在我会证明这些结论的时候，也是我即将退役的时候，哎。