给出一个n边形，用m种颜色给n边形的边上色，求有多少种方案能够使每两条相邻边不同色
题目解析
设有n个点时，方案数为A[n]。
一个一个点考虑，加入第n个点时：
其左右不同，则插入之前的方案数为A[n-1]，第n个点可以有m-2种选择。
其左右相同，在插入之前，则删掉其中一个点之后的的n-2个点是满足要求的方案，数量为A[n-2]，则n的颜色只需与相邻的不同，有m-1种方案。
综上，递推公式为A[n]=A[n-1]*(m-2)+A[n-2]*(m-1)。通项公式（特征根）：A[n]=(m-1)n+(m-1)*(-1)n。（快速幂）
代码#include<bits/stdc++.h>#defineLlonglongusingnamespacestd;Ln,m,ans=1,M=1e9+7;voidqpow(La,Lb){while(b){if(b&1)(ans*=a)%=M;(a*=a)%=M;b>>=1;}}ifstreamfin("color.in");ofstreamfout("color.out");intmain(){fin>>n>>m;qpow(m-1,n);if(n%2==0)(ans+=m-1)%=M;else(ans-=m-1)%=M;fout<<ans;}
