「成都七中D4T3」封尘的花环 - Polya计数+动态规划

题目大意

题目分析

为了叙述方便，下文将$[A]$表示$A$命题是否成立，成立返回$1$，否则返回$0$。

首先我们考虑循环同构的问题，我们可以用Polya计数来考虑它。
关于这一部分参考这里。

设$f[i]$为大小为$i$的不同花环数（不要求循环不同构）。
不难得出动态规划方程：

$$f[i]=(n-2)f[n-1]+(n-1)f[n-2]$$

如图，考虑$n-2$与$n$的颜色相同还是不同即可得出上述方程。

因此现在我们要求：

$$\begin{aligned} ans&=\frac 1n\sum_{i=1}^nf[\gcd(i,n)] \\ &=\frac 1n\sum_{d\mid n}f[d]\sum_{i=1}^n[\gcd(i,n)=d] \\ &=\frac 1n\sum_{d\mid n}f[d]\sum_{i=1}^{\lfloor \frac nd\rfloor}[\gcd(i,\lfloor \frac nd\rfloor)=1] \\ &=\frac 1n\sum_{d\mid n}f[d]\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{k\mid i,k\mid \lfloor\frac nd\rfloor}\mu(k) \\ &=\frac1n\sum_{d\mid n}f[d]\sum_{k\mid \lfloor\frac nd\rfloor}\mu(k)\lfloor \frac n{kd}\rfloor \\ &=\frac1n\sum_{d\mid n}f[d]\varphi(\lfloor \frac nd\rfloor) \end{aligned}$$

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int TIMES=10,maxn=105;
const LL mod=998244353;

LL Quick_Mul(LL a,LL b,LL p) {
	LL tmp=(a*b-(LL)((long double)a/p*b+1e-8)*p);
	if(tmp<0)return tmp+p;
	else return tmp;
}

LL Quick_Pow(LL a,LL b,LL p) {
	LL sum=1;
	for(a%=p; b; b>>=1,a=Quick_Mul(a,a,p))if(b&1)sum=Quick_Mul(sum,a,p);
	return sum;
}

LL Quick_Pow(LL a,LL b) {
	LL sum=1;
	for(a%= mod; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
	return sum;
}

mt19937 g(rand());

bool Witness(LL a,LL n) {
	LL u=n-1,t=0;
	while(u%2==0)t++,u>>=1;
	LL x=Quick_Pow(a,u,n);
	if(x==1)return false;
	for(int i=1; i<=t; i++,x=Quick_Mul(x,x,n))
		if(x!=n-1&&x!=1&&Quick_Mul(x,x,n)==1)return true;
	return x!=1;
}

bool Miller_Rabin(LL n) {
	if(n==2)return true;
	if(n<2||!(n&1))return false;
	for(int i=1; i<=TIMES; i++)
		if(Witness(g()%(n-1)+1,n))return false;
	return true;
}

LL Pollar_Rho(LL n) {
	if(!(n&1))return 2;
	while(true) {
		LL a=g()%(n-1)+1,b=a,c=g()%(n-1)+1;
		if(c==2)c=3;
		while(true) {
			a=(Quick_Mul(a,a,n)+c)%n;
			b=(Quick_Mul(b,b,n)+c)%n;
			b=(Quick_Mul(b,b,n)+c)%n;
			if(a==b)break;
			LL d=__gcd(abs(b-a),n);
			if(d>1)return d;
		}
	}
}

vector<LL>vec;

void Find_Fac(LL n) {
	if(Miller_Rabin(n)) {
		vec.push_back(n);
		return;
	}
	LL p=Pollar_Rho(n);
	Find_Fac(p);
	Find_Fac(n/p);
}

LL n,k,ans;
int cnt[maxn];

LL f(LL n) {
	return (Quick_Pow(k-1,n)+(k-1)*(n&1?-1:1))%mod;
}

void Dfs(int Depth,LL sum,LL phi) {
	if(Depth==vec.size()) {
		ans=(ans+phi%mod*f(n/sum))%mod;
		return;
	}
	LL tmp=1;
	for(int i=1; i<=cnt[Depth]; i++,tmp*=vec[Depth])Dfs(Depth+1,sum*tmp*vec[Depth],phi*tmp*(vec[Depth]-1));
	Dfs(Depth+1,sum,phi);
}

int main() {
	srand(time(NULL));
	int t=Get_Int();
	while(t--) {
		n=Get_Int();
		k=Get_Int();
		if(n==1) {
			printf("%d\n",k);
			continue;
		}
		vec.clear();
		Find_Fac(n);
		LL tmp=n;
		for(int i=0; i<vec.size(); i++) {
			cnt[i]=0;
			while(tmp%vec[i]==0) {
				tmp/=vec[i];
				cnt[i]++;
			}
		}
		ans=0;
		Dfs(0,1,1);
		printf("%lld\n",(ans*Quick_Pow(n,mod-2,mod)%mod+mod)%mod);
	}
	return 0;
}