自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:08:30，当前版本为作者最后更新于2022-02-14 07:37:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

理解本题解需要的前置知识：Pólya 定理、容斥原理。

可以发现本题分为两部分：

1. 求本质不同戒指数量。
2. 求本质不同项链数量。

先来看第一部分，求本质不同戒指数量：

戒指可以看做长度为 $m$ 的环，用 $r$ 种颜色进行染色，只存在旋转同构。这个东西其实就是 P4980 【模板】Pólya 定理，下面我们来推一下式子。

置换群 $G$ 为顺时针旋转 $0\sim m-1$ 个位置这些置换，答案即为在 $G$ 作用下等价类的数量。同时，定义集合 $M$ 为 $1\sim m$ 所有可能排列，就是初始的排列情况。

我们设 $c(g)$ 为置换 $g\in G$ 拆成的循环置换个数，那么旋转 $k$ 个位置的置换 $g$ 的循环置换个数为多少呢？$|g|=\frac{\textrm{lcm}(m,k)}{k}=\frac{m}{\gcd(m,k)}$，因此 $c(g)=\gcd(m,k)$。

根据 Pólya 定理，套路推式子得：

$$\begin{aligned} ans&=\frac{1}{|G|}\sum\limits_{g\in G}r^{c(g)}\\ &=\frac{1}{m}\sum\limits_{i=1}^mr^{\gcd(m,k)}\\ &=\frac{1}{m}\sum\limits_{i=1}^m\sum\limits_{d}r^d[\gcd(m,i)==d]\\ &=\frac{1}{m}\sum\limits_{d=1}^mr^d\sum\limits_{i=1}^{\frac{m}{d}}[\gcd(\frac{m}{d},i)==1]\\ &=\frac{1}{m}\sum\limits_{d\mid m}r^d\varphi(\frac{m}{d}) \end{aligned} $$

于是第一部分就做完了，假设上面这个答案为 $k$，再看第二部分，求本质不同项链数量：

如果不考虑特殊纪念品两侧不能相同，只考虑把戒指串成一条链时相邻不能相同，此时不难得到数量为 $k\cdot(k-1)^{n-1}$。但是特殊纪念品两侧还不能相同，怎么办呢？使用容斥，规定特殊纪念品两侧相同的方案数为 $n\gets n-1$ 的情况。

递归下去计算时间显然爆炸，我们可以手玩一下递归的过程，利用容斥的性质加减相消，不难找到规律，答案为 $(k-1)^n+(k-1)(-1)^n$，当然也可以使用特征方程等方式进行推导。

结合一下上面两部分，我们就可以得到最终的答案了。

放一份代码（仅供参考）：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll mod = 3214567;

ll n, m, r;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
ll qpow(ll x, ll y) {
	ll ans = 1;
	for(;y;y>>=1,x=x*x%mod) if(y & 1) ans = ans * x % mod;
	return ans;
}
ll inv(ll x) {return qpow(x, mod-2);}
ll phi(ll x) {
	ll ans = x;
	for(ll i=2;i*i<=x;i++) {
		if(!(x % i)) {
			ans = ans / i * (i - 1);
			while(!(x % i)) x /= i;
		}
	}
	if(x > 1) ans = ans / x * (x - 1);
	return ans;
}

int main() {
	scanf("%lld%lld%lld", &n, &m, &r);
	ll k = 0, lim = sqrt(m);
	rep(d, 1, lim) {
		if(!(m % d)) {
			k = (k + qpow(r, d) * phi(m/d) % mod) % mod;
			if(d != m / d) k = (k + qpow(r, m/d) * phi(d) % mod) % mod;
		}
	}
	k = k * inv(m) % mod;
	ll ans = (qpow(k-1, n) + ((n & 1) ? -1 : 1) * (k - 1) + mod) % mod;
	printf("%lld\n", ans);
	return 0;
}