WYF画了一个极为不规则的n边形，画面太美简直不看，没有任意两条边长度是相等的。因为形状太难看了，做他同桌的CWQ看不下去了，趁着WYF上厕所的时间准备用他书包里的m种颜色的彩笔给n边形的边上色。但由于WYF画的实在太大，CWQ不知如何下手，他想知道他有多少种染色方法，能够使得每两条相邻边不同色。你只需输出答案模10^9+7的结果。
一行，仅包含两个正整数n和m。
一个正整数，表示答案模10^9+7的结果
3 3
6
对于50%的数据，3≤n≤100000，3≤m≤10；
对于100%的数据，3≤n≤10^18，3≤m≤50。
可以先写一个暴力的程序，打表找规律（有时不得不承认打表是个好东西
）
方案数=(m-1)^n+(m-1)×(-1)^n。（快速幂）
这题DP只能拿50分
完整代码如下↓
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 using namespace std; 8 unsigned long long mod=1000000007; 9 unsigned long long sum=0,b; 10 unsigned long long f(unsigned long long x){//快速幂 11 if(x==0) return 1; 12 unsigned long long ans=f(x/2)%mod; 13 ans=ans*ans%mod; 14 if(x%2==1) ans=ans*b%mod; 15 return ans; 16 } 17 int main(){ 18 //freopen("color.in","r",stdin); 19 //freopen("color.out","w",stdout); 20 unsigned long long n,p; 21 cin>>p>>b; 22 if(p==1){//特判一下 23 cout<<b; 24 return 0; 25 } 26 b--; 27 sum+=f(p); 28 if(p%2==1) cout<<(sum-b)%1000000007; 29 else cout<<(sum+b)%1000000007; 30 }
原文：https://www.cnblogs.com/latent-Lin/p/13532940.html