T759 Valentine’s Coat
原题：（权限限制没有超链接）
题目描述 Description
今天是情人节，小杉在参加一个valentine’s party!
Oh,it sounds good.
现在已经是晚上10点了，参加party的n个人很无聊，于是开始玩一个游戏。
每个人先穿一件白外套，再站成一个圈，然后给每件外套上色。总共有k种颜色可以上。
一个可爱的上色方案应该满足对于每一个人，他身边的两个人所穿的外套颜色都和他所穿的不同。
小杉现在想知道总共有多少种可爱的上色方案。
输入输出格式 Input/output
输入格式：
一行两个整数n,k(1<=n<=3000,1<=k<=10)
输出格式：
仅有一行，一个整数，为上色方案数对19900801取模的结果
输入输出样例 Sample input/output
样例测试点#1 输入样例：
2 2
输出样例：
2
说明 description
譬如小杉和小小杉玩这个游戏，给小杉上第一种颜色，给小小杉上第二种颜色，或者相反，都是可爱的上色方案，总共两种。
个人解法：
开始想的很多，算了很久没有结果。着实要感谢一下pb大师，一点豁然开朗（其实我先点了他一下，然后他又点了我一下……）。
首先，我们把这个环看成一条链，那么条件就可以变为“一个长度为n的序列a，其中填入1至k的数，保证其中a[i]<>a[i-1]，a[1]<>a[n]。求有多少个这样的序列”。
如果不考虑a[1]<>a[n]，根据计数原理可以简单地求出一共有k*(k-1)^(n-1)种。
如果考虑a[1]<>a[n]的话，就应该要减去a[1]=a[n]的。而a[1]=a[n]的有多少种呢？同样是计数原理，我们可以把最后一个1视为固定，那么a[1]=a[n]的便有a[n-1]种（不是k*(k-1)^(n-2)种！想一想就明白了）。
所以我们就得出了递推式：
a[i]=k*(k-1)^(i-1)-a[i-1]
由于这里涉及了减法，那么我们取mod的时候，就要注意一下（设maxn是要取mod的数），因为可能有a mod maxn=ai，b mod maxn=bi。ai<bi但a>b。所以在每次减法后如果发现a[i]<0就inc(a[i],m*maxn)。m随意取，尽量大但有不超过longint。之后再mod就能保证答案正确了。
代码如下：
const
maxn=19900801;
var
a,func:array[0..3010] of longint;
n,k,i:longint;
begin
read(n,k);
func[1]:=k;
for i:=2 to n do//递推
begin
func[i]:=func[i-1]*(k-1) mod maxn;
a[i]:=func[i]-a[i-1];
if a[i]<0 then inc(a[i],maxn*5);//判断a[i]是否<0
a[i]:=a[i] mod maxn;
end;
writeln(a[n]);
end.
其实最初我是按照之前做过类似的一个题用树形图来推倒的。后来觉得很多东西其实不必复杂化，数学推论到极端了也不是一件好事……总之，就是不要为了方法而方法了。