Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 1815」「SHOI2006」color 有色图

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

Input

输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9

Output

即总数模P后的余数

Sample Input

1
3 2 97

Sample Output

1
4

Solution

考虑一种点的置换及其对应的边置换。

把点置换拆成若干个循环节。循环节具体包含了哪些节点不重要,重要的是每个循环节各包含几个元素。把这些「元素数」按顺序排好,记为 $L_1, L_2, \cdots , L_k$

把边分为两类:一个循环节内部的边、跨循环节的边。

对于循环节内部,每个边循环会覆盖 $L_i$ 条边,而循环节一共有 $\tbinom {L_i}{2}$ 条边。对于偶数个元素的循环,存在一个特殊的边循环节,它只包含 $L_i/2$ 条边。这样循环节的数目为 $\lfloor \frac{L_i}{2} \rfloor$

对于跨循环节的边,设两个节点所在的点循环分别包含 $L_i$$L_j$ 个点。一个循环会覆盖 $lcm (L_i, L_j)$ 条边。所以边循环总数就是 $\gcd(L_i, L_j)$

设循环总数为 k,则边的不动点数目为 $C=m^k$。

然后我们考虑有多少种点循环是上述特定 $L_1, L_2, \cdots , L_k$ 的形式。这相当于给所有 n 个点选择一种全排列,然后按顺序每 $L_i$ 个元素分成一组,问方案数。由题意,同一组内的元素也是要考虑顺序的,但如果循环同构,则算作同一种方案(因为是置换嘛)。如果相邻两组的元素数目相同,则它们不应区分顺序。所以方案数是

$$S=\frac{n!}{\prod_{i=1}^k L_i \times \prod_{i=1}^k B_{L_i}}$$

其中 $B_x$ 是 x 在 $L_1, L_2, \cdots , L_k$ 中出现的次数。

根据 Polya 定理,最终答案就是所有 C 的加权平均值。其中的「权」就是这种方案对应的 S。

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
#include <bits/stdc++.h>
using namespace std;
#define long long long
const int maxn = 55;
int n, m, gcd[maxn][maxn], L[maxn];
long mod, ans, tot;
long fac[maxn], finv[maxn], inv[maxn];
long quickpow(long a, long b) {
long ans = 1;
for (; b; b >>= 1) {
if (b & 1) (ans *= a) %= mod;
(a *= a) %= mod;
}
return ans;
}
void dfs(int p, int r) {
if (!r) {
long tmp = fac[n], ex = 0, cnt = 0;
--p;
for (int i = 1; i < p; ++i) for (int j = i + 1; j <= p; ++j) ex += gcd[L[i]][L[j]];
for (int i = 1; i <= p; ++i) ex += L[i] >> 1;
for (int i = 1; i <= p; ++i) {
(tmp *= inv[L[i]]) %= mod;
if (L[i] != L[i - 1]) (tmp *= finv[cnt]) %= mod, cnt = 0;
++cnt;
}
(tmp *= finv[cnt]) %= mod;
(tot += tmp) %= mod;
(tmp *= quickpow(m, ex)) %= mod;
(ans += tmp) %= mod;
return;
}
if (L[p - 1] > r) return;
for (int i = max(1, L[p - 1]); i <= r; ++i) {
L[p] = i;
dfs(p + 1, r - i);
}
}
int main() {
scanf("%d%d%lld", &n, &m, &mod);
for (int i = 0; i < maxn; ++i) for (int j = 0; j < maxn; ++j) gcd[i][j] = __gcd(i, j);
fac[0] = finv[0] = 1;
for (int i = 1; i < maxn; ++i) fac[i] = fac[i - 1] * i % mod, finv[i] = quickpow(fac[i], mod - 2), inv[i] = quickpow(i, mod - 2);
L[0] = 0;
dfs(1, n);
(ans *= quickpow(tot, mod - 2)) %= mod;
printf("%lld\n", ans);
return 0;
}
最近的文章

「BZOJ 3782」上学路线

Description小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短…

BZOJ, 中国剩余定理, 动态规划, 组合数 继续阅读
更早的文章

「BZOJ 4730」「UOJ 266」「清华集训2016」Alice和Bob又在玩游戏

DescriptionAlice和Bob在玩游戏。有n个节点,m条边(0&lt;=m&lt;=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。注:树的形态是在一开始就确定好的,…

BZOJ, 博弈论, 树型 DP 继续阅读