题解 P5233【[JSOI2012]爱之项链】

· · 题解

理解本题解需要的前置知识：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;
}