Yuanyuan Long and His Ballons

题目描述
Yuanyuan Long is a dragon like this picture?

I don’t know, maybe you can ask him. But I’m sure Yuanyuan Long likes ballons, he has a lot of ballons.
One day, he gets n white ballons and k kinds of pigment, and he thought a problem:

1. Number these ballons b1, b2, … , bi, …, to bn.

2. Link these ballons to a circle in order, and color these ballons.

3. He need to make sure that any neighbor ballons have different colors.

He wants to know how many solutions to solve this problem. Can you get the answer to him? The answer maybe very large, get the answer MOD 100000007.

For Example: with 3 ballons and 3 kinds of pigment

Your answer is 321 MOD 100000007 = 6.
The answer maybe large, you can use integer type long long.

输入描述:
The first line is the cases T. (T <= 100) For next T lines, each line contains n and
k. (2 <= n <= 10000, 2 <= k <= 100)

输出描述:
For each test case, output the answer on each line.

示例1

输入
3
3 3
4 2
5 3
输出
6
2
30

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

问题分析: 经典环形染色问题，只需代入公式 即可。
(公式推导过程: https://blog.nowcoder.net/n/26d37d711a3a4f2187b332b2ed687533)
注意n较大，使用快速幂可以防止超时，同时注意给变量定义long long型，防止计算过程中爆int。AC代码如下:

// 公式: ans = (k - 1)^n + (-1)^n * (k - 1)
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 100000007;

ll qmi(ll a, ll b)   // 快速幂
{
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        ll n, k;
        cin >> n >> k;

        int x;
        if(n & 1) x = -1;
        else x = 1;
        // 计算(-1)^n，赋给x

        ll ans = qmi(k - 1, n) + x * ((k - 1) % mod) % mod;
        // 根据(a + b) % mod = (a % mod + b % mod) % mod，保证计算过程中数据不会过大

        cout << ans << endl;
    }
    return 0;
}