Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「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 继续阅读