题解 P4916 【魔力环】

· · 题解

考虑Burside引理，设f(x)表示置换拆成循环的个数为x时的答案，那么最终的结果就是\displaystyle \frac{\sum_{i=1}^n f(gcd(i,n))}{n}，化简之后就是\displaystyle \frac{\sum_{d|n}f(d)\varphi(\frac{n}{d})}{n}。

考虑如何计算不动点的数量，为了方便首先把n=m的情况直接处理掉，那么现在问题变成了，把环上的点编号，所有模d相同的点都必须是同时染或者不染色，并且不能有连续的k个被染色。因为已经处理掉了n=m的情况，所以只需要至少有一个循环没有被染色，那么问题可以等价于有d个点要染其中的\frac{m}{d} 个，不能有连续的k个都被染色的方案数。

现在把要求的东西重新拿出来定义一下，即有N个球放成一圈，要给其中C个染色，不能有连续K个都被染色，求方案数。

我们把C个要染色的球拿出来，放进剩下的N-C个球组成的环的空隙之间，使得每个空隙里的球都不能超过K个。因为要确定的是标号，所以必须断环成链，那么第1个和第N-C个之间的空隙是第一个球之前和最后一个球之后这两段本质上是连在一起的，这两段加起来不能超过K个。

那么枚举第一个球之前和最后一个球之后这两段一共放了多少个球，然后前后分配一下，所以方案数就是：\displaystyle \sum_{i=0}^k (i+1)Put(C-i,N-C-1,K)，其中Put(C,N,K)表示把C个球分成N组，每组不能超过K个的方案数，这个东西可以用容斥在O(\frac{C}{K})的时间里解决，所以单次的复杂度不会超过O(\frac{N}{K}*K)=O(N)。

那么这样子总的复杂度就是O(n+\sigma(gcd(n,m))。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1000010
#define MOD 998244353
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
bool zs[MAX];
int pri[MAX],phi[MAX],tot;
int jc[MAX<<1],inv[MAX<<1],jv[MAX<<1];
void pre(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!zs[i])pri[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*pri[j]<=n;++j)
        {
            zs[i*pri[j]]=true;
            if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    jc[0]=jv[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=n+n;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=n+n;++i)jc[i]=1ll*jc[i-1]*i%MOD;
    for(int i=1;i<=n+n;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
}
int Choose(int n,int m){if(n<m||n<0||m<0)return 0;return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
int Put(int m,int n){if(m<0)return 0;return Choose(n+m-1,n-1);}
int n,m,K,p[MAX];
int Insert(int m,int n,int k)
{
    int ret=0;if(m<0)return 0;
    for(int i=0,d=1;i<=n;++i,d=MOD-d)
        if(m>=1ll*i*(k+1))ret=(ret+1ll*Put(m-i*(k+1),n)*Choose(n,i)%MOD*d)%MOD;
        else break;
    return ret;
}
int Calc(int d)
{
    int N=n/d,C=m/d,ret=0;
    if(C<=K)return Choose(N,C);
    if(K==1)return (Choose(N-C+1,C)+MOD-Choose(N-C-1,C-2))%MOD;
    for(int i=0;i<=K;++i)
        ret=(ret+1ll*(i+1)*Insert(C-i,N-C-1,K))%MOD;
    return ret;
}
int main()
{
    n=read();m=read();K=read();pre(n);
    if(n==m){if(K==n)puts("1");else puts("0");return 0;}
    if(!m){puts("1");return 0;}
    int g=__gcd(n,m),ans=0;
    for(int i=1;i*i<=g;++i)
        if(g%i==0)
        {
            ans=(ans+1ll*Calc(i)*phi[i])%MOD;
            if(i*i!=g)ans=(ans+1ll*Calc(g/i)*phi[g/i])%MOD;
        }
    ans=1ll*ans*fpow(n,MOD-2)%MOD;
    printf("%d\n",ans);
}