题解：P4916 [MtOI2018] 魔力环

· · 题解

一种不算简单的暴力推式子做法。

思路

由于求循环同构等价类个数，所以容易想到使用 Burnside 引理进行求解。

Burnside 引理部分

设 g_i 表示旋转 i 次。

假设要求 g_i 的不动点的个数，则从一个点向其将要到达的点连边会获得 \gcd(i, n) 个大小为 \frac{n}{gcd(i, n)} 的小环，这些环要求单个环内颜色相同，同时满足题目限制。

由于这些环内颜色相同，所以可以缩成一个大点，并且将 n, m 除以环的大小。

缩完之后考虑怎么满足题目的限制，由于每个环其实是由模 \gcd(i, n) 意义下的一个等价类，那么一个环拿出来一个元素作为代表的话，这些元素是构成一个环的。

设 f(n, m, k) 为 n 个点 m 个黑点，不能出现 k 个以上连续黑点的环的数量（不考虑循环同构）。

所以答案是：

\frac{1}{n}\sum_{i = 1}^{n}{f(\gcd(i, n), \frac{m \gcd(i, n)}{n}, k)} = \frac{1}{n}\sum_{i | n, i | m}{f(\frac{n}{i}, \frac{m}{i}, k)\varphi(i)}

后面的式子由前面的式子枚举 \frac{n}{\gcd(n, i)} 得到。

环上计数部分

现在的问题就是如何求出 f(n, m, k) 了。

由于要求的是对连续黑点大小的限制，那我们可以将每一段连续的相同颜色缩起来，这样就是黑白交替的了。

容易发现除了颜色全部相同之外（特判即可），其他的方案都使得缩完后的点数是偶数个。

那么可以去枚举有多少个黑色连通块，此时白色连通块数量与黑色一致，假设是 i 个。

先不考虑标号的问题，也不考虑谁黑谁白，并给每个联通块标号（其实就是每个连通块是不同的）。

那么白色连通块的总方案数为 \binom{n - m - 1}{i - 1}，这个可以通过插板法得到。

此时黑色连通块总方案数就不一样了，由于白色连通块方案数是直接统计 x_1 + x_2 + \cdots + x_i = n - m 的解数，但是黑色连通块还有一个限制是 x \leq k，这东西考虑容斥掉，枚举钦定有多少满足 x > k 的得到方案数为：

\sum_{j = 0}^{i}{(-1)^j \binom{m - jk - 1}{i - 1} \binom{i}{j}}

这个上界看着很难受，其实可以直接抬升到 n 的。

先获得一个比较劣的做法，回来考虑点有标号怎么办。

其实也挺好办的，直接绕着环赋值，然后将这个环一直转圈就好了，也就是给答案乘上 n，吗？

其实在枚举了 i 时做出的假设就导致了：一个合法的状态，将所有的黑白连通块转两次仍然是合法的（转一下会导致黑白颠倒，算不同方案）。

此时发现当所有的点在转圈统计答案的时候，如果跳出了当前连通块，就等价于将所有的连通块反向转一次，所以这样就导致一个方案被统计了 i 次，所以需要将其除掉。

所以可得：

f(n, m, k) = n\sum_{i = 1}^{\frac{n}{2}}{\sum_{j = 0}^{n}{(-1)^j \binom{m - jk - 1}{i - 1} \binom{i}{j} \binom{n - m - 1}{i - 1} \frac{1}{i}}}

直接做有点太劣了，考虑优化（以下推式子用到了较多组合数性质，请谨慎观看）。

由于 min(m, n - m) \leq \frac{n}{2}，所以其实上界可以都开到 n。

令 T = m - jk - 1。

\begin{aligned} f(n, m, k) &= n\sum_{i = 1}^{\frac{n}{2}}{\sum_{j = 0}^{n}{(-1)^j \binom{T}{i - 1} \binom{i}{j} \binom{n - m - 1}{i - 1} \frac{1}{i}}} \\ &= n\sum_{i = 1}^{n}{\sum_{j = 0}^{n}{(-1)^j \binom{T}{i - 1} \binom{i - 1}{j - 1} \frac{i}{j} \binom{n - m - 1}{i - 1} \frac{1}{i}}} \\ &= n\sum_{j = 0}^{n}{(-1)^j \frac{1}{j} \sum_{i = 1}^{n}{\binom{T}{i - 1} \binom{i - 1}{j - 1} \binom{n - m - 1}{i - 1}}} \\ &= n\sum_{j = 0}^{n}{(-1)^j \frac{1}{j} \sum_{i = 1}^{n}{\binom{T}{j - 1} \binom{T - j + 1}{i - j } \binom{n - m - 1}{i - 1}}} \\ &= n\sum_{j = 0}^{n}{(-1)^j \frac{1}{j} \binom{T}{j - 1} \sum_{i = 1}^{n}{\binom{T - j + 1}{i - j } \binom{n - m - 1}{n - m - 1 - i + 1}}} \\ &= n\sum_{j = 0}^{n}{(-1)^j \frac{1}{j} \binom{T}{j - 1} \binom{T - j + n - m}{n - m - j}} \\ &= n\sum_{i = 0}^{n}{(-1)^i \frac{1}{i} \binom{T}{i - 1} \binom{T - i + n - m}{n - m - i}} \\ \end{aligned}

需要注意，该式子在 i = 0 时是错误的，所以需要特殊处理一下。

这样就是 O(\sigma(n)) 的了。

记得特判只有一种颜色的情况。

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <bitset>
#include <algorithm>
#include <map>
#include <iomanip>
#include <cassert>
#include <unordered_map>
#include <set>
#include <random>
#include <queue>

using namespace std;

const int N = 2e5 + 10, mod = 998244353;

#define int long long

#define fi first
#define se second
#define emp emplace_back

using pii = pair <int, int>;
using ld = long double;
using ll = long long;
const int inf = 0x3f3f3f3f;
const ld eps = 1e-9;

int fac[N], inv[N];

int C(int n, int m) {if (n < 0 || m < 0) return 0; return n >= m ? fac[n] * inv[m] % mod * inv[n - m] % mod : 0;}

int qpow(int x, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * x % mod;
        x = x * x % mod;
        b >>= 1;
    }
    return res;
}

int calc(int n, int m, int k)
{
    int flag = 1, ans = 0;
    for (int j = 1; j <= n / 2; j++)
    {
        flag = 1;
        for (int i = 0; i <= 0; i++)
        {
            (ans += flag * C(m - i * k - 1, j - 1) % mod * C(j, i) % mod * C(n - m - 1, j - 1) % mod * qpow(j, mod - 2) % mod) %= mod;
            flag = mod - flag;
        }
    }
    flag = mod - 1;
    for (int i = 1; i <= n; i++)
    {
        int T = m - i * k - 1;
        if (T < 0) continue;
        (ans += flag * qpow(i, mod - 2) % mod * C(T, i - 1) % mod * C(T - i + 1 + n - m - 1, n - m - i) % mod) %= mod;
        flag = mod - flag;
    }
    return n * ans % mod;
}

int phi(int x)
{
    int ans = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i) continue;
        ans = ans / i * (i - 1);
        while (x % i == 0) x /= i;
    }
    if (x != 1) ans = ans / x * (x - 1);
    return ans;
}

int n, m, k;

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m >> k;
    if (m == 0)
    {
        cout << 1 << '\n';
        return 0;
    }
    if (n == m)
    {
        cout << (n <= k) << '\n';
        return 0;
    }
    fac[0] = inv[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
    int ans = 0;
    for (int i = 1; i * i <= n; i++)
    {
        if (n % i) continue;
        if (m % i == 0) ans += calc(n / i, m / i, k) * phi(i) % mod;
        if (i * i != n && m % (n / i) == 0) ans += calc(i, m / (n / i), k) * phi(n / i) % mod;
    }
    cout << ans % mod * qpow(n, mod - 2) % mod << '\n';

    return 0;
}