Question

n条边染m种颜色,相邻的边颜色不同,有几种情况（边着色问题），求思路

n染色
Time Limits: 1000 ms Memory Limits: 262144 KB
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。

Answer 1

首先,将它想象成首尾相接,第二个格子开始选色一直选到最后一个,有两种情况:第二个与最后一个颜色一样或不同.假设涂n个格子方法为Fn,Fn=(m-2)Fn-1+(m-1)Fn-2,(加号两边对应两种情况,相当于一个递推式,颜色相同那种情况,第二个和最后一个看成一个格子,就相当于涂n-2的情况）然后就是将其换成通项,F1=0,F2=m(m-1) (F1的情况首尾相当于同色所以是0),以下利用特征根（若不清楚,可以查一下）,得出Fn=(-1)^(n-1)A+(m-1)^(n-1)B,利用F1,F2可得出A=1-m,B=m-1
带入Fn即可,答案正确已验证.若有不清楚可再问我,

Answer 2

🍡🍡🍡🍡🍡