题解 P4916 【魔力环】

· · 题解

题意：n 个珠子的手环满足如下条件：

两个手环旋转后相同，则本质相同。求本质不同的手环的种类数。

答案对 998244353 取模，n,m,k\leq 10^5，时限 \texttt{1s}。

upd 2025.2.27：重新排版，修改了一处错误。

首先特判全黑的情况（n=m）。

看到环与旋转，容易想到 Burnside 引理。

设 g(t) 为旋转 t 步，符合题意的不动点个数。答案为

{\rm Ans}=\frac{1}{n}\sum_{t=1}^ng(t)

设 f(c) 为：不动点要求的等价关系形如 c 个交错环，填写黑白的方案数。则 g(t)=f\big(\gcd(t,n)\big)。

{\rm Ans}=\dfrac{1}{n}\sum\limits_{t=1}^nf\big(\gcd(t,n)\big)

现在考虑如何求 f(c)。

等价类（形如交错的环）的个数为 c，相当于点 i 的等价类编号为 i\bmod c。

如下 n=12,c=4 的情形：

0123 | 0123 | 0123

那么每连续 c 个元素（循环节）可以看成一个小环（大小为 n/c)，因为左右能与其他一模一样的循环节相接。

设 $S(N,M)$ 为：在一个大小为 $N$ 的环上，染 $M$ 个黑色，不能有超过 $k$ 个连续黑色的方案数。 有 $$ f(c)=[c|n,m]S(n/c,m/c) $$ ----- 现在考虑如何求 $S(N,M)$。 考虑把 $M$ 个黑球放进 $N-M$ 个白球的 $N-M+1$ 个空隙内。 由于是环，第一个空隙和最后一个空隙共享限制，它们的黑球个数加起来不过 $k$。枚举它们共放多少个黑球： $$ S(N,M)=\sum\limits_{i=0}^k(i+1)R(N-M-1,M-i) $$ 其中 $R(N,M)$ 是：在 $N$ 个盒子里放 $M$ 个球，盒子容量上限为 $k$ 的方案数。代表剩余的缝隙。 系数 $(i+1)$ 是因为：$i$ 个球可以有一部分放在第一个空隙，一部分放在最后一个空隙。 ----- 考虑如何计算 $R(N,M)$。 考虑容斥。令某些盒子超过容量，容易发现盒子之间没有顺序关系，有： $$ R(N,M)=\sum_{i=1}^{\min(M/k,N)}(-1)^i\dbinom{N}{i}T\big(N,M-i(k+1)\big) $$ 其中，$T(N,M)$ 为把 $M$ 个球放进 $N$ 个有标号盒子中的方案数，这用组合数学很好算。 ----- 复杂度分析。 容斥计算 $R(N,M)$ 的复杂度是 $O(M/k)$。 回看 $S(N,M)=\sum_{i=0}^k(i+1)R(N-1,M-i)$，需要求 $O(k)$ 个 $R$，复杂度$O(M)$。 回看 $$ \begin{aligned} {\rm Ans} &=\dfrac{1}{n}\sum_{t=1}^nf\big(\gcd(t,n)\big)\\ &=\frac{1}{n}\sum_{d|n}f(d)\varphi(n/d)\\ &=\frac{1}{n}\sum_{d|n,d|m}\varphi(n/d)S(n/d,m/d) \end{aligned} $$ 复杂度是 $O(\sigma(m))$（$m$ 的约数之和）。 > 注： > - 易证 $\sigma(m)=O(m\log m)$。因为约数最差情况下形如 $m/1,m/2,m/3,\dots
  • 进一步地，可证 \sigma(m)=O(m\log\log m)。

代码如下：

#include <algorithm>
#include <cstdio>

const int MaxN = 100050, mod = 998244353;

int powM(int a, int t=mod-2) {
    int ret = 1;
    while(t) {
        if (t&1)
            ret = 1ll*ret*a %mod;
        a = 1ll*a*a %mod;
        t >>= 1;
    }
    return ret;
}
int fac[MaxN], ifac[MaxN];
int C(int n, int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void Init(int n) {
    fac[0] = 1;
    for (int i=1; i<=n; i++)
        fac[i] = 1ll*fac[i-1]*i %mod;
    ifac[n] = powM(fac[n]);
    for (int i=n; i; i--)
        ifac[i-1] = 1ll*ifac[i]*i %mod;
}

int T(int n,int m) {
    return C(n+m-1, n-1);
}
int K;
int R(int n,int m) {
    int ans=0;
    for (int i=0; i<=std::min(m/(K+1),n); i++) {
        if (i&1)
            ans =(ans-1ll*C(n,i)*T(n,m-i*(K+1))) %mod;
        else
            ans =(ans+1ll*C(n,i)*T(n,m-i*(K+1))) %mod;
    }
    return (ans+mod)%mod;
}
int S(int n, int m) {
    if (m<=K) return C(n,m);
    int ans = 0;
    for (int i=0; i<=std::min(K,m); i++)
        ans = (ans+1ll*R(n-m-1,m-i)*(i+1)) %mod;
    return ans;
}

int phi(int n) {
    int ans = n;
    for (int i=2; i*i<=n; i++)
        if (n%i==0) {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    if (n>1) ans = ans/n*(n-1);
    return ans;
}
int gcd(int a, int b) {
    return !b ? a : gcd(b, a%b);
}

int main() {
    int n, m;
    scanf("%d%d%d", &n, &m, &K);
    if (n==m) {
        puts(K>=m ? "1" : "0");
        return 0;
    }
    Init(n);
    int D = gcd(n,m), ans = 0;
    auto calcFactor = [&ans,n,m](int d) -> void {
        ans = (ans + 1ll*S(n/d,m/d)*phi(d)) %mod;
    };
    for (int i=1; i*i<=D; i++)
        if (D%i==0) {
            calcFactor(i);
            if (i*i!=D)
                calcFactor(D/i);
        }
    ans = 1ll*ans*powM(n)%mod;
    printf("%d", ans);
    return 0;
}