JZOJ 4248. 【五校联考7day1】n染色

题目

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

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 }

为何要逼自己长大，去闯不该闯的荒唐