N染色 本题基本都打表过的，我来一个数学推导 ——————————————————————————————————————
对 于 新 的 一 条 边 ， 与 这 条 边 相 邻 的 边 可 能 相 同 也 可 能 不 同 ， 对于新的一条边，与这条边相邻的边可能相同也可能不同， 对于新的一条边，与这条边相邻的边可能相同也可能不同， 若 不 同 ， 即 为 d p [ n − 1 ] 的 方 案 数 ， 而 本 条 边 就 有 m − 2 种 填 法 若不同，即为dp[n-1]的方案数，而本条边就有m-2种填法 若不同，即为dp[n−1]的方案数，而本条边就有m−2种填法 若 相 同 ， 即 为 d p [ n − 2 ] 的 方 案 数 ， 填 满 n − 2 条 边 ， 此 时 加 进 第 n − 1 条 边 ， 则 n − 1 条 边 和 第 1 条 边 颜 色 相 同 ， 则 第 n 条 边 有 m − 1 种 填 法 若相同，即为dp[n-2]的方案数，填满n-2条边，此时加进第n-1条边，则n-1条边和第1条边颜色相同，则第n条边有m-1种填法 若相同，即为dp[n−2]的方案数，填满n−2条边，此时加进第n−1条边，则n−1条边和第1条边颜色相同，则第n条边有m−1种填法 所 以 , d p [ n ] = ( m − 2 ) ∗ d p [ n − 1 ] + ( m − 1 ) ∗ d p [ n − 2 ] 所以,dp[n]=(m-2)*dp[n-1]+(m-1)*dp[n-2] 所以,dp[n]=(m−2)∗dp[n−1]+(m−1)∗dp[n−2] 但 n = 3 时 是 特 例 ， 以 为 与 第 三 条 边 相 邻 的 第 一 条 和 第 二 条 颜 色 一 定 不 等 ， 所 以 我 们 可 以 把 d p [ 1 ] = 0 ， d p [ 2 ] = m ∗ （ m − 1 ） 但n=3时是特例，以为与第三条边相邻的第一条和第二条颜色一定不等，所以我们可以把dp[1]=0，dp[2]=m*（m-1） 但n=3时是特例，以为与第三条边相邻的第一条和第二条颜色一定不等，所以我们可以把dp[1]=0，dp[2]=m∗（m−1） —————————————————————————————————— 详见必修5，根据递推方程， 我 们 得 到 通 项 d p n = A ∗ ( m − 1 ) n + B ∗ ( − 1 ) n 我们得到通项dp_n=A*(m-1)^n+B*(-1)^n 我们得到通项dpn=A∗(m−1)n+B∗(−1)n 代 入 d p [ 1 ] , d p [ 2 ] 即 可 解 出 通 项 代入dp[1],dp[2]即可解出通项 代入dp[1],dp[2]即可解出通项 最 后 得 到 d p [ n ] = ( m − 1 ) n + ( m − 1 ) ∗ ( − 1 ) n 最后得到dp[n]=(m-1)^n+(m-1)*(-1)^n 最后得到dp[n]=(m−1)n+(m−1)∗(−1)n —————————————————————————————————————
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod=1e9+7;ll n,m; ll ksm(ll x,ll pow){ ll ans=1,res=x%mod; while(pow){ if(pow&1) ans=ans*res%mod; res=res*res%mod; pow>>=1; } return ans; } int main(){ scanf("%lld%d",&n,&m); ll tmp;if(n%2==1) tmp=1-m;if(n%2==0) tmp=m-1; ll sum=ksm(m-1,n); ll ansout=sum+tmp; printf("%lld",ansout); }