题解 P5233 [JSOI2012]爱之项链

· · 题解

洛谷题面传送门

首先很明显题目暗示我们先求出符合条件的戒指数量，再计算出由这些戒指能够构成的项链的个数，因此考虑分别计算它们。首先是计算符合条件的戒指数量，题目中“可以通过旋转重合的戒指视作相同”可以让我们联想到 Polya 定理，具体来说根据 Polya 那套理论，符合条件的戒指个数就是 C=\dfrac{1}{m}\sum\limits_{d\mid n}R^d\varphi(\dfrac{n}{d})，\mathcal O(\sqrt{n}) 地枚举因子并计算 \varphi 即可。注意这里 m 有可能是 3214567 的倍数，对于这种情况，我们考虑将模数变成 3214567^2，这样计算完之后除以 m 这一步可以先令乘上 \dfrac{m}{3214567} 在模 3214567^2 意义下的逆元，然后答案除以 3214567（虽然似乎数据没有这样的情况？）

接下来考虑此题的第二部分，如何通过符合条件的戒指数量 C 计算项链个数，一个很 naive 的想法是 C·(C-1)^{n-1}，不过由于“纪念品两侧戒指不同”这一条件的存在，这个想法是错误的。正确的方法是，设 f_i 表示长度为 i 的满足条件的项链个数，我们考虑从纪念品一侧的戒指开始，给 i 枚戒指分别标号 1,2,3,\cdots,i，那么我们考虑分 1 和 i-1 戒指相同 与 1 和 i-1 戒指不同这两类进行处理，对于 1,i-1 戒指不同的情况，如果我们把戒指 i 拿掉，其余戒指组成了长度为 i-1 的符合条件的项链，而由于 1,i-1 戒指不同，第 i 个戒指的方案数就是 C-2，总方案数 f_{i-1}·(C-2)，对于 1,i-1 戒指相同的情况，由于 i-2,i-1 相邻，i-2,i-1 戒指必定不同，故 1,i-2 对应的戒指也不同，因此如果我们把 i-1,i 戒指拿掉，那剩余 i-2 个戒指还是可以组成长度为 i-2 的符合条件的项链，这部分的贡献也就是 f_{i-2}·(C-1)。因此我们可以得到递推式 f_i=f_{i-1}·(C-2)+f_{i-2}·(C-1)，边界条件 f_1=0,f_2=C(C-1)，直接暴力推是 \mathcal O(n) 的，无法通过，不过很明显对于这样 f_i=af_{i-1}+bf_{i-2} 的递推式，我们可以通过特征根方程优化，具体来说我们求出 x^2=ax+b 的两根 \alpha,\beta，那么 f_i 统统可以表示为 A\alpha^i+B\beta^i 的形式。此题也不例外，代入 a=C-2,b=C-1 可得特征根方程两根 \alpha=-1,\beta=C-1，再代入 f_1=0,f_2=C(C-1) 可得 A=(C-1),B=1，因此 f_i=(C-1)(-1)^n+(C-1)^n。

u1s1 感觉此题和这题出奇地相似，题解写得也出奇地相似（

ll n,MMOD=MOD;int m,r;
ll getmul(ll x,ll y){return (__int128_t)(1)*x*y%MMOD;}
int qpow(int x,ll e){
    int ret=1;
    for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
    return ret;
}
ll _qpow(int x,int e){
    ll ret=1;
    for(;e;e>>=1,x=getmul(x,x)) if(e&1) ret=getmul(ret,x);
    return ret;
}
void exgcd(ll x,ll y,ll &a,ll &b){
    if(!y) return a=1,b=0,void();exgcd(y,x%y,a,b);
    ll tmp=a;a=b;b=tmp-(x/y)*b;
}
ll getinv(ll a,ll mod){
    ll x,y;exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
int getphi(int x){
    int res=x,tmp=x;
    for(int i=2;i*i<=x;i++) if(tmp%i==0){
        res=res/i*(i-1);
        while(tmp%i==0) tmp/=i;
    } if(tmp>1) res=res/tmp*(tmp-1);
    return res;
}
int main(){
    scanf("%lld%d%d",&n,&m,&r);ll ret=0;
    bool flg=0;if(m%MOD==0) flg=1,MMOD=1ll*MOD*MOD;
    for(int i=1;i*i<=m;i++) if(m%i==0){
        ret=(ret+getmul(_qpow(r,i),getphi(m/i)))%MMOD;
        if(m/i!=i) ret=(ret+getmul(_qpow(r,m/i),getphi(i)))%MMOD;
    } ret=1ll*ret*getinv((flg)?(m/MOD):m,MMOD)%MMOD;
    if(flg) ret/=MOD,ret%=MOD;
    printf("%d\n",(1ll*(ret-1)*qpow((MOD-1),n)%MOD+qpow(ret-1,n))%MOD);
    return 0;
}