https://atcoder.jp/contests/abc284/tasks
Ex - Count Unlabeled Graphs
按照下面步骤生成图
选 简单,无向,n个无标签点 的图
给每个点 写 <= k的数, (1~k每个都至少出现一次
找方案数 mod p(质数 1e8~1e9)
范围
k <= n <= 30
我的思路
无标签的图 和 有标签的图之间 如何进行 重复统计的转化 ???
考虑按照连通块来划分
连通块大小 和 同联通块大小的选择个数
f[s] = 每个连通块大小为s 的 染色方案数 的生成方程 = a[s] x^s + a[2s] x^2s + a[3s] x^3s …
为了统计 g[s] = 加上外部贡献的选择倍数 = a[s]/s! x^s + a[2s]/(2s)! x^2s + a[3s]/(3s)! x^3s …
这样 ans = [x^n] n! g[1] * g[2] * g[3] * ... * g[n]
那么问题来了, 如何计算f[i]
h[i] = 1个大小为i的联通块的染色方案数
a[i] = h[i], 直接染色
a[2i] = binom(2i,i-1) h[i] * h[i], 确定1在地一个块
a[3i] = binom(3i,i-1) * binom(2i,i-1) h[i]^3, 确定1在地一个块, 不在第一个块中最小的在第二个块
那么如何计算h[i]
count[形状] = 一个形状的染色方案数
h[i] = sum count[形状i]
形状不同, 染色后一定不同, 但是相同形状 染色后可能相同,
如何判断两个形状不同, 如何枚举形状, 每个形状如何计算染色方案??????????????????????????
并不会
能想到一些必要条件, 但没啥充分条件, 比如 点i连的点和相同,且度相同
题解
上面考虑的过程还是差了一个 正好k个颜色
考虑 <= k个颜色的方案, 再算正好k = sum binom(k,i) (-1)^{k-i} (<=i的方案) 容斥一下
然后 无标签图难以处理, 先考虑带标签图
$S_n=$ n的排列的集合
子问题: 多少个n点带标签图, 点值在[1..k], 如果 一个图 通过某个$p\in S_n$ 映射了值和边以后 得到另一个图,认为它们相等
$G$ 所有有标签的图, (点上无值)
对于有标签的图$g\in G$, $p(g)$ 表示 $g$的 点经过排列$p$映射后的图
$A(g) = $ G 中能通过 排列映射得到g 的 图的数量
$B(g) = $ 就是g通过 排列映射后 还是g的 排列数
那么有 $A(g)B(g) = N!$
右侧就是 $g$ 和所有排列作用
而注意到 任何图 经过$p$ 变换后 它的”形状”没有变, 所以 B(g) == B(p(g))
所以 A(g) 对应的每个图 都是 B(g) 个变化, 且都能通过某个p(g)得到
根据一一映射得证
例子: 图 g=(1-2,3), 那么A(g) = 3, B(g) = 2
A(g): 的3个图 (1-2,3),(1-3,2),(1,2-3),
B(g): 的2个排列 (1,2,3),(2,1,3)
3 * 2 = 6 = 3!
Pólya enumeration theorem (applied to this problem)
令 G’ 为(从G中去掉标签后的无向图)的集合.
那么有 $|G’| = \frac{\sum_{p \in S_n} \vert \lbrace g \vert g \in G, p(g) = g \rbrace \vert}{N!}$
证明这个等式相等:
G中每个生成 无标签的图 只会在G’ 中出现一次, 对于无标签图 g’, 有 A(g) 个图 在g中和它对应(通过去掉标签)
例如 o-o,o 和 1-2,3,1-3,2,1,2-3
$|G’| = \sum_{g \in G} \frac{1}{A(g)} $
$= \frac{1}{N!} \sum_{g \in G} \frac{N!}{A(g)} $
$= \frac{1}{N!} \sum_{g \in G} B(g)$
$= \frac{1}{N!} \sum_{g \in G} \vert \lbrace p \vert p \in S_n, p(g) = g \rbrace \vert$
$= \frac{1}{N!} \sum_{g \in G} \sum_{p \in S_n} \lbrack p(g) = g \rbrack$
$= \frac{1}{N!} \sum_{p \in S_n} \sum_{g \in G} \lbrack p(g) = g \rbrack$
$= \frac{1}{N!} \sum_{p \in S_n} \vert \lbrace g \vert g \in G, p(g) = g \rbrace \vert$
这样, 我们可以 消除 “isomorphic up to labels,” 的情况, 简单的做objects统计, 像这个问题, 一个组合问题 需要 identify graphs up to permutations 可以通过 不动点 的 平均值 解决. 这样的技巧 在cycle或cube中的组合问题中也使用了,如 ABC198F. (Pólya’s theorem 同样成立, 当用在 排列的集合 上时.)
证明: $g’$ 表示 $g$ 去掉标签后的图, $t(g’)$ 表示给这个无向图每个点放值的方案数
$ans = \sum_{g’\in G’} t(g’) = \sum_{g \in G} \frac{1}{A(g)} t(g’) $
$= \frac{1}{N!} \sum_{g \in G} \frac{N!}{A(g)} t(g’) $
$= \frac{1}{N!} \sum_{g \in G} B(g) t(g’)$
$= \frac{1}{N!} \sum_{g \in G} \vert \lbrace p \vert p \in S_n, p(g) = g \rbrace \vert t(g’)$
$= \frac{1}{N!} \sum_{g \in G} \sum_{p \in S_n} \lbrack p(g) = g \rbrack t(g’)$
$= \frac{1}{N!} \sum_{p \in S_n} \sum_{g \in G} \lbrack p(g) = g \rbrack t(g’)$
这里 就变成按一个具体的有标签的$g$, 来统计, 也就是说 如果 $t(g_1’)$和$t(g_2’)$ 的到相同结果, 都会被统计, 只是 同一个$g$ 去标签 再给点赋值 得到的重复的 只统计一次,
显然 如果有一个g’中的点赋值方案, 至少有一个g中的点赋值方案对应, 问题是 是否存在g中两个点赋值方案 对应到 同一个g’的点赋值方案,
而这里保证这点的反而是这个p, 因为在p的关系下, “有标签”的作用 其实变成了 对无标签的图形的唯一标识!!!??? 啊就很神奇,
这样, 对于每个给定的p, 计算 有标签图 $p(g) = g$ 的个数, 并求平均值(就是乘上1/n!). 排列可以表示成 环的大小,$(c_1, c_2, \dots, c_m)$, 这样的图的数量为
$K^m \times 2^{\sum_{i=1}^m \left(\lfloor c_i/2\rfloor + \sum_{j=1}^{i-1} \gcd(c_i, c_j)\right) }$
在排列的同一个环上的数都一样, 所以是K^m, 接下来是有自由度的边, 如果 环i中pi 和 环j中pj相连, 那么 环i中的 (pi+w)%len(环i) 和 (pj+w)%len(环j)相连, 所以一个环和前面的环相连的自由边 是 $\gcd(c_i,c_j)$, 可以连或不然后就是环内自己, 考虑环内(pi) 和(pi+w)连, 那么w的的范围是$\lfloor \frac{c_i}{2} \rfloor$
$= \frac{1}{N!} \sum_c \sum_{\mathrm{cycle}(p)= c} \sum_{g \in G} \lbrack p(g) = g \rbrack t(g’)$
和abc226f 一样, 枚举n的所有分割(每次让当前最小的在新的环中), 然后加起来(按环表示对应的排列数) $\times$ (上面的值). 可以 O(p(N) poly(N)) 算出来, p(n) 是 n-th 分割数,
按环表示对应的排列数, 考虑 大小s有x个, 在选值时 有 binom{n}{s,s,…,s} 种, 然后它们之间每个方案中每组s用最小的表示, 所以轮换还有 m!, 所以 需要 1/(m!s^m)
代码
https://atcoder.jp/contests/abc284/submissions/38141401
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
| #include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int T=100;
vector<mint> fac;
vector<mint> ifac;
mint binom(int n,int m){return (n<m or m<0)?0:(fac[n] * ifac[n-m] * ifac[m]);}
mint dfs(int n,int K, int last, vector<pair<int, int>> &v) {
if (n == 0) {
mint ans = 1;
rep(i,0,size(v)){
auto [cyc1, num1] = v[i];
ans /= fac[num1] * (mint{cyc1}.pow(num1));
ans *= mint{K}.pow(num1);
ans *= mint{2}.pow(cyc1 / 2 * num1 + cyc1 * num1 * (num1 - 1) / 2);
rep(j,0,i) {
auto [cyc2, num2] = v[j];
ans *= mint{2}.pow(gcd(cyc1, cyc2) * num1 * num2);
}
}
return ans;
}else{
mint ans = 0;
rep(nxt,last+1,n+1) for (int i = 1; nxt * i <= n; i++) {
v.push_back({nxt, i});
ans += dfs(n-nxt*i, K, nxt, v);
v.pop_back();
}
return ans;
}
}
mint f(int n,int k){
vector<pair<int, int>> v;
return dfs(n,k,0,v);
}
int main() {
int n=read();
int K=read();
mint::set_mod(read());
fac.assign(T+1,1);
rep(i,1,T+1) fac[i] = fac[i - 1] * i;
ifac.resize(T+1);
ifac[T] = fac[T].inv();
per(i,0,T) ifac[i] = ifac[i + 1] * (i + 1);
mint ans = 0;
rep(k,1,K+1) ans+=f(n,k)*binom(K, k)*(((K-k)&1)?-1:1);
printf("%d\n",ans.val());
return 0;
}
|
总结
Ex
有想过 标签的图 和 无标签的图的 转化, 但没想出具体怎么搞
学了一手 A(g)B(g) = N!
这个 无标记图个数 = avg (每个排列 的 不动图 个数) 怎么就能直接知道 无标记点有值个数 = avg(每个排列 的 点有值不动图 个数) ????????????????????????????????????????
然后就是与无标签图和有标签图有关的 polya 定理
$\sum_{g’\in G’} t(g’) = \frac{1}{N!} \sum_{p \in S_n} \sum_{g \in G} \lbrack p(g) = g \rbrack t((g)’)$
然后这里的 p(g)=g 的作用下 其实是让g在g’中唯一标识, 所以同个g的 不同点上赋值 对应的g’的点上赋值一定不同
参考
官方题解
abc 226f
luogu p4727