[比赛][递推][计数DP] 2018 ICPC 徐州网络赛 A Hard to prepare

比赛时候一直想推通式，然而并没有成功，和队友两个人用两种思路推出来两个公式。。。然后最后得知答案的通式是分奇偶性的，每个公式正好对一半，呵呵。。。。。

就题目本意来讲应该是dp。先把圆环展开为链，然后考虑一个满足题意的局面，这时候最后一位客人的面具与第一位客人的面具的关系决定了这条链是否能形成符合要求的环。如果一开始用两个状态分别表示最后一位与第一位冲突以及最后一位与第一位不冲突的两种情况，则会发现无法继续往后转移，因为从n位摆到n+1位的方法数是会受到前一位与第一位是否相同的影响的，因此需要再加一个状态信息，三个状态信息分别表示，最后一位与第一位相同，最后一位与第一位冲突，既不相等也不冲突，三种情况下的方案数，写出状态转移方程即可。

#include 

using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int mod=1e9+7;

LL dp[maxn][4];

LL getpow(int k)
{
    LL res=1;
    for (int i=1;i<=k;i++)
    {
        res*=2;
        if(res>mod)
            res%=mod;
    }
    return res%mod;
}

int main()
{
    int T,n,k;
    LL m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        m=getpow(k);
        if(n==1)
        {
            printf("%lld\n",m);
            continue;
        }
        if(k==1)
        {
            printf("2\n");
            continue;
        }
        dp[1][0]=m;
        dp[1][1]=0;
        dp[1][2]=0;
        for (int i=2;i<=n;i++)
        {
            dp[i][0]=(dp[i-1][0]+dp[i-1][2])%mod;
            dp[i][1]=(dp[i-1][1]+dp[i-1][2])%mod;
            dp[i][2]=((m-3)*dp[i-1][2]%mod+(m-2)*dp[i-1][1]%mod+(m-2)*dp[i-1][0]%mod)%mod;
        }
        printf("%lld\n",((dp[n][0]+dp[n][2])%mod+mod)%mod);
    }
    return 0;
}