传送门

表示这种\(Burnside\)定理之类的东西一用就忘qwq

题目要求不同染色方案数,因为变换方式只有旋转,所以只有\(n\)个置换,然后可能会出现某种方案有循环节,这个循环节长度显然要是\(\gcd(n,m)\)的因数,我们枚举循环节个数,直接套个polya然后可以得到答案为\(\frac{\sum_{d|\gcd(n,m)}f(\frac{n}{d},\frac{m}{d})\varphi(d)}{n}\),其中\(f(n,m)\)为有\(n\)个珠子,要把\(m\)个染色,并且满足最长连续的黑色个数以及首尾黑色个数\(\le k\)的方案

这个东西,可以考虑把白色的珠子提出来,然后枚举首尾放了多少个黑色\(i\),这样有\(i+1\)种方案,剩下的黑色就要放在\(n-m-1\)个空位中,并且满足一个空位不超过\(k\)个黑色.这个可以容斥,枚举一些位置已经超过\(k\)个,然后剩下随便放.这个式子长这样:$$\sum_{i=0}^{{k}(i+1)\sum_{j=0}}{n-m-1}(-1)^j\binom{n-m-1}{j}g(m-i-j*(k+1),n-m-1)$$

其中\(g(n,m)\)表示\(n\)个一样的物品放进\(m\)个不一样的盒子的方案数,也就是\(\binom{n+m-1}{m-1}\)

代码巨丑

#include<bits/stdc++.h>

#define LL long long

#define db long double

#define il inline

#define re register

using namespace std;

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

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int fac[N],iac[N];

int C(int n,int m){return m<0||n<m?0:1ll*fac[n]*iac[m]%mod*iac[n-m]%mod;}

int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int n,m,nn,kk,prm[20],nm[20],tt,ans;

int wk(int n,int m)

{

	if(m<=kk) return C(n,m);

	int an=0,l=n-m-1;

	for(int i=0;i<=kk;++i)

	{

		int nw=0;

		for(int j=0;j<=l&&m-i-j*(kk+1)>=0;++j)

		{

			int x=1ll*C(l,j)*C(m-i-j*(kk+1)+l-1,l-1)%mod;

			nw=(nw+((j&1)?mod-x:x))%mod;

		}

		an=(an+1ll*nw*(i+1)%mod)%mod;

	}

	return an;

}

void dfs(int o,int d,int phi)

{

	if(o>tt)

	{

		ans=(ans+1ll*wk(n/d,m/d)*phi%mod)%mod;

		return;

	}

	dfs(o+1,d,phi);

	for(int i=1;i<=nm[o];++i)

	{

		d*=prm[o];

		dfs(o+1,d,phi*(prm[o]-1)*fpow(prm[o],i-1));

	}

}

int main()

{

	fac[0]=1;

	for(int i=1;i<=N-10;++i) fac[i]=1ll*fac[i-1]*i%mod;

	iac[N-10]=fpow(fac[N-10],mod-2);

	for(int i=N-10;i;--i) iac[i-1]=1ll*iac[i]*i%mod;

	n=rd(),m=rd(),kk=rd();

	if(n==m) return printf("%d\n",(bool)!kk),0;

	nn=gcd(n,m);

	int x=nn,sqt=sqrt(nn);

	tt=0;

	for(int i=2;i<=sqt&&x>1;++i)

		if(x%i==0)

		{

			prm[++tt]=i,nm[tt]=0;

			while(x%i==0) ++nm[tt],x/=i;

		}

	if(x>1) prm[++tt]=x,nm[tt]=1;

	ans=0,dfs(1,1,1);

	printf("%lld\n",1ll*ans*fpow(n,mod-2)%mod);

    return 0;

}