题目传送门
bzoj1815 - [Shoi2006]color 有色图（双倍经验）
题解
暴力
由于在做题之前已经被告知是 Burnside 引理，貌似思考的时候少了一些乐趣啊。
考虑一个置换 \(p\)，想要求出这个置换下的不动点的个数。对于一个不动点，若存在一条边 \((a, b)\)，一定存在一条边 \((p_a, p_b)\)。
那么考虑一个长度为 \(l\) 的循环，若 \((i, j)\) 是一条 \(i, j\) 均在循环中的点内部的边，那么所有距离等于 \(i, j\) 的距离的点对之间都会有一条边。这样，我们一共可以将这些边分成 \(\frac x2\) 中内部绑定的组。因此，一个长度为 \(l\) 的循环可以产生 \(2^{\frac x2}\) 种方案的贡献。
下面考虑一条两个端点分别在长度为 \(x\) 的循环和 \(y\) 的循环上的边。这样的话，一条边的两个端点在两个循环上走，一直到下一次两个端点都与原来的两个端点重合。显然对于一组点，会走过 \(\operatorname{lcm}(x, y)\) 个点。于是，一共有 \(\frac {xy}{\operatorname{lcm}(x, y)} = \gcd(x, y)\) 组。贡献为 \(2^{\gcd(x, y)}\) 种方案。
优化
但是暴力算法显然会 TLE。
我们一个置换的贡献仅取决于它的每一个循环的长度，因此我们只需要知道它的每一个循环的长度就可以求出贡献了。
于是我们可以使用 Burnside 引理相关题目的常见套路。
我们用 \(B(n)\) 来表示整数划分的方案数。整数划分是指将 \(n\) 划分为若干个无序的正整数的和。当 \(n=100\) 时，\(B(n)\) 大概是 1e6。当 \(n = 40\) 时大概是 \(4e4\) 左右，\(n=45\) 时候大约 \(9e4\)。
因此，由于本题 \(n=45\)，如果暴力枚举划分的话，不会超过 \(9e4\) 次。
那么我们如果枚举出 \(n=\sum \limits_{i=1}^k L_i\)，那么方案相当于是从 \(n\) 个位置中选出 \(L_1\) 个位置作为第一个循环的成分，再从剩下的 \(n-L_1\) 个位置中选出 \(L_2\) 个……
因此对于这样的划分，其方案数是：
&\binom n{L_1} \binom{n-L_1}{L2} \binom{n-L_1-L_2}{L_2}\cdots\\
=&\frac{n!}{\prod \limits_{i=1}^k Li!}
\end{align*}
\]
（实际上也可以从可重复元素的全排列的角度考虑
然后求出来划分的方案数以后，我们还需要把每一个数放进这些被安排好的位置，使得每一段真的是一个循环。一个循环的第一个数可以考虑连接到这一段剩余的 \(L-1\) 个位置的任何一个位置。然后对于刚刚选择的那个位置，它又可以连接到剩余的 \(L-2\) 个位置。因此对于一个长度为 \(L\) 的循环，它的合法安排数字的方案数为 \((L-1)!\)。
但是还有一个小问题，如果有两个长度相同的置换，他们是没有什么先后区别的，但是在用之前的组合计算方法的时候，会产生先后的区别。这是不应该产生的。因此令 \(C_i\) 表示等于 \(i\) 的 \(L\) 值的个数。我们还需要乘上 \(C_i!\)。
因此对于一个整数划分的总方案数为：
\]
然后就是和暴力一样的计算不动点的个数了。
最终答案为：
\]
下面是代码。由于 \(\gcd\) 和 \(2\) 的正整数幂均可以预处理，因此总的时间复杂度为 \(O(B_n\cdot n^2)\).
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I>
inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 200 + 7;
const int P = 997;
int n, ans, hkk;
int inv[N], fac[N], ifac[N << 1], pw[N], gcd[N][N];
int l[N];
inline void sadd(int &x, int y) { x += y; x >= P ? x -= P : x; }
inline int smod(int x) { return x >= P ? x - P : x; }
inline void ycl() {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % P;
inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (ll)(P - P / i) * inv[P % i] % P;
ifac[0] = 1; for (int i = 1; i <= n; ++i) ifac[i] = (ll)ifac[i - 1] * inv[i] % P;
pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = smod(pw[i - 1] << 1);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
if (!i || !j) gcd[i][j] = i ^ j;
else gcd[i][j] = gcd[j][i % j];
gcd[j][i] = gcd[i][j];
// dbg("%d %d %d\n", i, j, gcd[i][j]);
}
}
}
inline void calc(int div) {
int cnt = 1;
for (int i = 1; i <= l[0]; ++i) cnt = (ll)cnt * pw[l[i] / 2] % P;//, dbg("l[%d] = %d, %d\n", i, l[i], pw[l[i] / 2]);
for (int i = 1; i <= l[0]; ++i)
for (int j = 1; j < i; ++j) cnt = (ll)cnt * pw[gcd[l[i]][l[j]]] % P;//, dbg("*****************");
sadd(ans, (ll)cnt * div % P);
}
inline void dfs(int n, int lim, int div) {
// dbg("n = %d, lim = %d, div = %d\n", n, lim, div);
if (!n) return calc(div);
for (int i = std::min(lim, n); i; --i) {
int df = div;
for (int j = 1; i * j <= n; ++j) {
df = (ll)df * inv[i] % P, l[++l[0]] = i;
dfs(n - i * j, i - 1, (ll)df * ifac[j] % P);
}
while (l[l[0]] == i) --l[0];
}
}
inline void work() {
ycl();
ans = 0;
dfs(n, n, 1);
printf("%d\n", ans);
}
inline void init() {
read(n);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}
附录 - bzoj1815 - [Shoi2006]color 有色图 代码
发现只需要把上面的有/无的状态改为 \(k\) 中颜色就可以了。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I>
inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 53 + 7;
int n, k, P, ans;
int inv[N], fac[N], ifac[N << 1], pw[N], gcd[N][N];
int l[N];
inline void sadd(int &x, int y) { x += y; x >= P ? x -= P : x; }
inline int smod(int x) { return x >= P ? x - P : x; }
inline void ycl() {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % P;
inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (ll)(P - P / i) * inv[P % i] % P;
ifac[0] = 1; for (int i = 1; i <= n; ++i) ifac[i] = (ll)ifac[i - 1] * inv[i] % P;
pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = (ll)pw[i - 1] * k % P;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
if (!i || !j) gcd[i][j] = i ^ j;
else gcd[i][j] = gcd[j][i % j];
gcd[j][i] = gcd[i][j];
// dbg("%d %d %d\n", i, j, gcd[i][j]);
}
}
}
inline void calc(int div) {
int cnt = 1;
for (int i = 1; i <= l[0]; ++i) cnt = (ll)cnt * pw[l[i] / 2] % P;//, dbg("l[%d] = %d, %d\n", i, l[i], pw[l[i] / 2]);
for (int i = 1; i <= l[0]; ++i)
for (int j = 1; j < i; ++j) cnt = (ll)cnt * pw[gcd[l[i]][l[j]]] % P;//, dbg("*****************");
sadd(ans, (ll)cnt * div % P);
}
inline void dfs(int n, int lim, int div) {
// dbg("n = %d, lim = %d, div = %d\n", n, lim, div);
if (!n) return calc(div);
for (int i = std::min(lim, n); i; --i) {
int df = div;
for (int j = 1; i * j <= n; ++j) {
df = (ll)df * inv[i] % P, l[++l[0]] = i;
dfs(n - i * j, i - 1, (ll)df * ifac[j] % P);
}
while (l[l[0]] == i) --l[0];
}
}
inline void work() {
ycl();
ans = 0;
dfs(n, n, 1);
printf("%d\n", ans);
}
inline void init() {
read(n), read(k), read(P);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}