P4708 画画 题解

· · 题解

可以枚举 n! 种置换，求出每种置换下的不动点个数。

而每条边又分在相同置换和不同置换内两种

相同置换内求不动点个数

在一个置换内的不动点个数是 \frac{n}{2}，考虑如果有边 (x,x+t)，那么必有边 (x+1,x+t+1)\cdots% 以此类推。并且考虑 t 与 n-t 其实是等价的。

不同置换内求不动点个数

考虑两个置换的大小为 A,B，那么一条边会引申出 \operatorname{lcm}(A,B) 条边，于是不动点个数其实是 \gcd(A,B)。

而这些等价类可以出现可以不出现，对答案的贡献是 2^{cnt}。

发现只与置换的大小有关，暴力枚举拆分，算每个拆分的方案数，先有一个排列的方案数 n!，一个循环的贡献是 \frac{1}{len}，大小相同的循环之间无序，有一个 \frac{1}{cnt_{i}!}。

考虑欧拉回路这个更强的限制，即每个点的度数为偶数，同样考虑一个置换内的边。

考虑一个置换间的边 对一个 A 中的点度数的影响是 \frac{B}{\gcd(A,B)}，对 B 中的影响是 \frac{A}{\gcd(a,b)}。

我们发现现在可以先将贡献乘上没有影响的 2^{cnt}。

然后可以有 d_id 种方法使第 i 个置换的度数全部 +1，e_{u,v} 中方法使 u,v 置换的度数都 +1。

然后就是求使得满足限制的方案数，可以高斯消元异或矩阵，贡献为最后的自由元个数。

但还有更好的方法。

我们对现在 e_{u,v} 形成的连通块，随便求一棵生成树，生成树外的边随便选，除根以外的点随便选。

发现根和树边对应着唯一的可行解。

点数为 n，点的选择数为 s，边的选择数为 m 的一个连通块。

方案数就是 2^{m-(n-1)+\max(0,(s-1))}。

用并查集维护即可。

主要就是求不动点个数，考虑在一个置换内或置换间的不动点，暴力枚举拆分数乘上方案数，通过一个生成树的构造快速求得可行解个数，挺巧妙的。

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int Mod = 998244353;
int add (int a, int b) {
    return a + b >= Mod ? a + b - Mod : a + b;
}
int mul (int a, int b) {
    return 1ll * a * b % Mod;
}
int dec (int a, int b) {
    return a - b < 0 ? a - b + Mod : a - b;
}
int ksm (int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = mul (a, a)) if (b & 1) ans = mul (ans, a);
    return ans;
}
void Add (int &a, int b) {
    a = add (a, b);
}
cs int N = 55;
int gcd (int a, int b) {
    return !b ? a : gcd (b, a % b);
}
int n, ans, inv[N], g[N][N];
int fa[N], sm[N];
int find (int x) {
    return x == fa[x] ? x : fa[x] = find (fa[x]);
}
int loop[N], ct[N], now;
int calc() { //计算
    int res = 0;
    for (int i = 1; i <= now; i++) fa[i] = i, sm[i] = 0;
    for (int i = 1; i <= now; i++) {
        int v = loop[i];
        res += ((v - 1) >> 1);
        if (! (v & 1)) sm[i] = 1;
    }
    for (int i = 1; i <= now; i++) {
        for (int j = i + 1; j <= now; j++) {
            int u = loop[i], v = loop[j], gc = g[u][v];
            int a = (u / gc) & 1, b = (v / gc) & 1;
            if (a && b) fa[find (i)] = find (j), res += gc;
            if (a && !b) sm[j] += gc;
            if (!a && b) sm[i] += gc;
            if (!a && !b) res += gc;
        }
    }
    for (int i = 1; i <= now; i++)
        if (find (i) == i) {
            ++res;
            res += sm[i] == 0 ? 0 : sm[i] - 1;
        } else sm[find (i)] += sm[i];
    res -= now;
    return ksm (2, res);
}
void dfs (int las, int rest, int coef) { //dfs枚举
    if (!rest) {
        Add (ans, mul (coef, calc()));
        return;
    }
    for (int i = min (las, rest); i; i--) {
        ++ct[i];
        loop[++now] = i;
        dfs (i, rest - i, mul (coef, mul (inv[i], inv[ct[i]])));
        --ct[i];
        --now;
    }
}
int main() {
    cin >> n;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = mul (Mod - Mod / i, inv[Mod % i]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = gcd (i, j);
    dfs (n, n, 1);
    cout << ans;
    return 0;
}