科普：环形染色公式（中间不染色）的推导

我们先把他当链做：这样有 $m (m-1)^{n-1}$ 种做法。

在变成环，分类讨论：

1. $1$ 和 $n$ 相同这样就有 $f_{n-1}$ 种方案

2. 反之，为 $f_n$ 种做法

所以 $f_n+f_{n-1}=m(m-1)^{n-1}$ 。

还可以化：

$$f_n+f_{n-1}=m(m-1)^{n-1}=(m-1+1)(m-1)^{n-1}=(m-1)^n+(m-1)^{n-1} $$

移项，得

$$f_n-(m-1)^n=-(f_{n-1}-(m-1)^{n-1})$$

我们令 $b_n={f_n-(m-1)^n}$，你会发现

$\large \frac{b_n}{b_{n-1}}=-1$，所以 $b$ 是个等比数列。

当 $n=2$ 时，显然，$f_2=m(m-1)$，则

$$b_2=f_2-(m-1)^2=m(m-1)-(m-1)^2=m-1$$

所以 $b_n=b_2 \times (-1)^{n-2} = (-1)^n\times (m-1)$

又因为 $f_n=b_n+(m-1)^n$，

所以 $f_n=(m-1)^n+(-1)^n\times(m-1)$。

如果你不想推公式。

钦定中间块颜色，转化成环染色。直接讨论 $1$ 与 $n-1$ 是否相同，如果相同，把 $1$ 到 $n-1$ 看成一个块，答案是 $(m-2)f(n-2)$，如果不同，直接忽略 $n$，令 $1$ 与 $n-1$ 相接，答案是 $(m-3)f(n-1)$。于是有 $f(n)=(m-2)f(n-2)+(m-3)f(n-1)$，矩阵加速即可。

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int MOD=1e9+7;
int n,m;
struct matrix{
	int n,m;
	int num[2][2];
	matrix operator*(const matrix& mtrx)const{
		matrix res={n,mtrx.m,{{0,0},{0,0}}};
		if(m!=mtrx.n) return res;
		for(int i=0;i<n;i++)
			for(int j=0;j<mtrx.m;j++)
				for(int k=0;k<m;k++)
					(res.num[i][j]+=num[i][k]*mtrx.num[k][j])%=MOD;
		return res;
	}
}I={2,2,{{1,0},{0,1}}},A,T,Ans;
matrix qpow(matrix x,int b){
	matrix res=I;
	for(;b;b>>=1,x=x*x) if(b&1) res=res*x;
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin>>n>>m){
		if(n==1){
			cout<<m*(m-1)%MOD<<'\n';
			continue;
		}
		A={2,1,{{(m-1)*(m-2)%MOD},{0}}};
		T={2,2,{{m-3,m-2},{1,0}}};
		Ans=qpow(T,n-2)*A;
		cout<<Ans.num[0][0]*m%MOD<<'\n';
	}
	return 0;
}