题目

   

Description

WYF画了一个极为不规则的n边形，画面太美简直不看，没有任意两条边长度是相等的。因为形状太难看了，做他同桌的CWQ看不下去了，趁着WYF上厕所的时间准备用他书包里的m种颜色的彩笔给n边形的边上色。但由于WYF画的实在太大，CWQ不知如何下手，他想知道他有多少种染色方法，能够使得每两条相邻 边不同色。你只需输出答案模10^9+7的结果。  

Input

一行，仅包含两个正整数n和m。

Output

一个正整数，表示答案模10^9+7的结果  

Sample Input

3 3

Sample Output

6  

Data Constraint

对于50%的数据，3≤n≤100000，3≤m≤10； 对于100%的数据，3≤n≤10^18，3≤m≤50。

分析

找规律

     设有 n 个点时，方案数为 A[n]。 一个一个点考虑，加入第 n 个点时： 其左右不同，则插入之前的方案数为 A[n-1]，第 n 个点可以有 m2 种选择。 其左右相同，在插入之前，则删掉其中一个点之后的的 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。 （快速幂） 50 分方法：枚举 n，m，用动态规划看每个点标每个颜色时的方 案数。

代码

 

1 #include<iostream> 2 //#define cin fin 3 //#define cout fout 4 #define ll long long 5 #define M 1000000007 6 using namespace std; 7 //ifstream fin("color.in"); 8 //ofstream fout("color.out"); 9 ll n,m; 10 ll ans; 11 void ksm(ll a,ll b) 12 { 13 ans=1; 14 ll x=a; 15 while (b) 16 { 17 if (b&1) ans*=x; 18 ans%=M; 19 x*=x; 20 x%=M; 21 b>>=1; 22 } 23 } 24 int main () 25 { 26 cin>>n>>m; 27 ksm(m-1,n); 28 if (n%2==0) (ans+=m-1)%=M; 29 else 30 (ans-=m-1)%M; 31 cout<<ans%M; 32 }

 

转载于:https://www.cnblogs.com/zjzjzj/p/10339615.html

相关资源：数据结构—成绩单生成器