环染色方案数

题目描述

有一个大小为 $n$ 的环，要求给环上每个节点染色为 $1 \sim k$ 中的某种颜色，使得任意两个相邻的节点颜色不同，询问染色的方案数。答案对 $10^9+7$ 取模。

数学推导

注意到 $n,k\leq10^9$，连数组都开不了，于是我们考虑数学（~~还有数列大佬嘿嘿嘿~~）。

定义 $A_n$ 表示染色方案数，如右图：

若 $1,n-1$ 不同色，方案数为 $(k-2)A_{n-1}$
若 $1,n-1$ 同色，方案数为 $(k-1)A_{n-2}$

$$\therefore A_n=(k-2)A_{n-1}+(k-1)A_{n-2}$$

考虑到 $A_1=k$ 不满足上式，令 $a_n=A_{n+1},a_1=k(k-1),a_2=k(k-1)(k-2)$，也有：

$$a_n=(k-2)a_{n-1}+(k-1)a_{n-2} \ ①$$

熟悉的待定系数法，仿照斐波那契数列，设 $a_n+\mu a_{n-1}=\lambda (a_{n-1}+\mu a_{n-2})\ ②$

联立 $①②$，有

$$\begin{cases} \lambda -\mu=k-2 \newline \lambda\mu=k-1
\end{cases}$$

很简单的方程，凑完全平方即可，取其中一个解

$$\begin{cases} \lambda=k-1 \newline \mu=1
\end{cases}$$

代入 $②$：$a_n+a_{n-1}=(k-1)(a_{n-1}+a_{n-2})$

令 $b_n=a_{n+1}+a_n$，则 $b_n=(k-1)b_{n-1},b_1=a_1+a_2=k(k-1)^2$

$\therefore b$ 是以 $k(k-1)^2$ 为首项，$q=(k-1)$ 的等比数列，$b_n=b_1q^{n-1}=k(k-1)^{n+1}$

$$\therefore a_{n+1}+a_n=k(k-1)^{n+1} \ ③$$

继续使用待定系数法，注意到 $n+1$ 出现在 $k$ 的指数上面，则对于 $a_n$ 也应该有个 $(k-1)^n$，即要多乘一个 $(k-1)$，于是设

$$a_{n+1}+m(k-1)=-(a_n+m) \ ④$$

联立 $③④$，解得 $m=-(k-1)^{n+1}$

$$\therefore a_{n+1}-(k-1)^{n+2}=-(a_n-(k-1)^{n+1})$$

令 $c_n=a_n-(k-1)^{n+1}$，则 $c_n=-c_{n-1},c_1=a_1-(k-1)^2=k-1$

$$\therefore c_n=(k-1)\cdot(-1)^{n-1}$$

$$a_n=(k-1)^{n+1}+(-1)^{n-1}\cdot(k-1)$$

$$A_n=a_{n-1}=(k-1)^n+(-1)^n(k-1)$$

收工！

代码

这本质上是个数学题，推出结论后就没什么难点了，唯一值得注意的地方是 $n\leq10^9$，直接暴力求幂肯定会超时，于是使用快速幂（~~这就不用我讲了吧……~~）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,k;
int pow(int a,int x){
    int r=1;
    while(x){
        if(x&1) r=r*a%mod;
        a=a*a%mod;
        x>>=1; 
    }
    return r%mod;
} 
signed main(){
    int t;
    cin>>t;
    while(t--){
        scanf("%lld%lld",&n,&k);
        if(n==1) printf("%lld\n",k); 
        else printf("%lld\n",(pow(k-1,n)+((n&1)?(1-k):(k-1))+mod)%mod);
    } 
    return 0;
}