Color 圆盘染色

题目大意：给你一个圆盘，等分成n个扇形，有m种颜色，每两个相邻的扇形不能颜色不能相同，求染色方案数。

注释：m,n<=$10^6$.

想法：这题是小圆盘染色的加强版（小圆盘染色？），想法和那道题类似，只不过是一个更一般的形式。同样的想法，我们采用一种分划（分划？猛戳看黄字）。给定一个起始扇形。显然，这道题我们的疑惑就在于最后一个扇形与起始扇形的颜色是否相同。所以，我们期望考虑倒数第二个扇形的颜色。倒数第二个扇形的颜色无非就是两种：1.和起始扇形颜色相同。2.和起始扇形颜色不同。这两种显然就是本题的一种分划。那么，我们分别考虑：我们记录 a [i] 表示有i个扇形时的染色方案数。

　　如果倒数第二个扇形与起始扇形颜色相同，我们就暂时将起始扇形、倒数第一个扇形和倒数第二个扇形看成一个扇形（因为这个大扇形的左右两个小扇形的颜色是相同的，剩下i-3个扇形对倒数第1个扇形没有影响），此时的方案数为a[i-2]，又因为倒数第一个扇形被两个相同颜色的扇形夹住了，所以此时有(m-1)*a[i-2]种方案。

　　另一种情况：此时倒数第2个扇形与起始扇形颜色不相同。那么此时，即使将倒数第一个扇形去掉，剩下的扇形也是满足题意的，而且此时倒数第一个扇形有(m-2)种染色方法，所以此时有(m-2)*a[i-1]，种染色方法。

　　综上，我们可以得出：$a_i=(m-1)\cdot a_{i-2}+(m-2)\cdot a_{i-1}$.

下面，附上丑陋的代码......

#include <iostream>

#include <cstdio>

#define mod 20102010

using namespace std;

long long a[1000100];

int main()

{

    long long m,n;

    scanf("%lld%lld",&m,&n);

    a[1]=m;

    a[2]=(m-1)*m%mod;

    a[3]=(m*(m-1))%mod*(m-2)%mod;

    for(int i=4;i<=n;i++)

    {

        a[i]=(a[i-1]*(m-2)%mod+a[i-2]*(m-1)%mod)%mod;

    }

    printf("%lld\n",a[n]);

    return 0;

}

小结：错误

　　1.千万要搞清楚n,m的输入顺序。

　　2.由于n,m的数据范围，两数相乘是容易爆int，所以，开long long;