【2018 徐州网络赛】 Hard to prepare （递归 + 思维）

After Incident, a feast is usually held in Hakurei Shrine. This time Reimu asked Kokoro to deliver a Nogaku show during the feast. To enjoy the show, every audience has to wear a Nogaku mask, and seat around as a circle.

There are N guests Reimu serves. Kokoro has $2^k2k masks numbered from 0,1,cdots,0,1,⋯, 2^k - 12k−1, and every guest wears one of the masks. The masks have dark power of Dark Nogaku, and to prevent guests from being hurt by the power, two guests seating aside must ensure that if their masks are numbered ii and jj , then ii XNOR jj must be positive. (two guests can wear the same mask). XNOR means ~(ii^jj) and every number has kk bits. (11 XNOR 1 = 11=1, 00 XNOR 0 = 10=1, 11 XNOR 0 = 00=0)$

You may have seen 《A Summer Day's dream》, a doujin Animation of Touhou Project. Things go like the anime, Suika activated her ability, and the feast will loop for infinite times. This really troubles Reimu: to not make her customers feel bored, she must prepare enough numbers of different Nogaku scenes. Reimu find that each time the same guest will seat on the same seat, and She just have to prepare a new scene for a specific mask distribution. Two distribution plans are considered different, if any guest wears different masks.

In order to save faiths for Shrine, Reimu have to calculate that to make guests not bored, how many different Nogaku scenes does Reimu and Kokoro have to prepare. Due to the number may be too large, Reimu only want to get the answer modules

Input

First line one number

Output

For each testcase output one line with a single number of scenes Reimu and Kokoro have to prepare, the answer modules

样例输入

2
3 1
4 2

样例输出

2
84

SOLUTION:

看起来也像是一个高中的组合数学题目。手动模拟一下可以发现，对于每一个二进制数，有且仅有一个与之对应的二进制数跟他的同或和为0，因此如果每个人旁边只有一种帽子不能放，其他的都可以放。假设有m种帽子，m=2km=2k
第一个人有m种放法，第二人不能跟跟他同或为0，所以只有m-1种放法，以此类推，第n-1个人也有m-1种放法。然后是最后一个，因为最后一个不仅取决于第n-1个还取决于第1个，所以我们还要看第n-1个和第1个情况

1.如果第n-1个与第1个不相同的话，那么还是按照我们上面说的，第1个人放m种，第2个人放m-1…第n-1个人放m-1，最后一个人因为既要和第1个同或大于0，又要和第n-1个同或大于0，所以只有m-2种。那么一共就是m(m−1)..(m−1)(m−2)m(m−1)..(m−1)(m−2)
2.如果第n-1个与第1个相同的话，那么这个时候我们这样看。首先把问题分解成
（在第1个人和第n-1个人相同的情况下，前n-1个人的种类）*（第n个人能分到的种类）
然后先看后面的“第n个人分到的种类”，显然由于第1个和第n-1个人是一样的，那么第n个人的种类就是m-1.
那前面的种类怎么算呢？前提条件是第1个和第n-1个是一样的，然后中间随便放，而且题目要求的是围成一圈，所以我们画个图看看，会发现首位是一样的，那么我们可以将他们看成是一个整体，因为对结果没有影响。那现在前面一半的种类数就化成了当n=n-2时候的一个子问题。

CODE:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9 + 7;
ll n, k, m;
ll pow_m(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a%mod;
        a = a * a%mod;
        b = b >> 1;
    }
    res = res % mod;
    return res;
}
ll solve(int n)
{
    if (n == 1) return m;
    if (n == 2) return m * (m - 1) % mod;
    return  (m*pow_m(m - 1, n - 2) % mod*(m - 2) + solve(n - 2)) % mod;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld", &n, &k);
        m = pow_m(2, k);
        printf("%lld
", solve(n));
    }
    return 0;
}