ACM-ICPC 2018 徐州赛区网络预赛 A. Hard to prepare 圆形排列染色

题目链接：https://nanti.jisuanke.com/t/A2000
题目大意：有n个人和(2^k)种不同颜色帽子。每种帽子有无数顶。问：使所有人和相邻的人的帽子都不同的方案数？

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;

LL qpow(LL a, LL b){
    if(!a) return 0;
    LL ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

LL pow2[1000005]={1};
LL DP(LL n, LL k){
    if(n==1) return pow2[k];
    if(n==2) return pow2[k]*(pow2[k]-1)%mod;
    LL ans=(pow2[k]*qpow(pow2[k]-1, n-2)%mod)*(pow2[k]-2);
    ans=(ans+mod+DP(n-2, k))%mod;
    return ans;
}

int main() {
    for(int i=1; i<1000005; i++){
        pow2[i]=pow2[i-1]*2%mod;
    }
    int T; scanf("%d", &T);
    while(T--){
        int n, k; scanf("%d%d", &n, &k);
        printf("%lld\n", DP(n, k));
    }

    return 0;
}