ICPC 2018 徐州网络预赛 A. Hard to prepare

【题目链接】

样例输入
2
3 1
4 2
样例输出
2
84

解题思路

1. 0~2^k-1中，任何一个数对应的同或和为0的数有且仅有一个。
2. 首先会想到第一个有2^k种放法，第二个至第n-1个有2^k-1种放法。
3. 至于第n个，假设第一个数和倒数第二个数不相等，那么最后一个数有2^k-2种放法。
4. 如果倒数第二个数和第一个数相等呢？显然最后一个数字有2^k-1种放法，由于在第三点时已经计算过2^k-2种放法了，所以这里认为最后一个数字是一个定值，所以我们还需要加上ans[n-2]，然后整个做法就出来了，注意先预处理2的次幂，不然容易超时。
5. 结论：ans[n]=2^k * (2^k-1)^(n-2) * (2^k-2) + ans[n-2]
   
   

AC代码

#include <iostream>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll power_mod(ll a, ll b)
{
    a %= mod;
    ll base = a;
    ll res = 1LL;
    while (b)
    {
        if (b & 1)
            res = (base * res) % mod;
        base = (base * base) % mod;
        b = b >> 1;
    }
    return res % mod;
}
ll ans[1000005];
ll pow2[1000005];
void init()
{
    pow2[0] = 1;
    for (int i = 1; i < 1000005; i++)
        pow2[i] = (pow2[i - 1] * 2) % mod;
}
int main()
{
    init();
    int t;
    ll n, k;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld", &n, &k);
        ans[1] = pow2[k];
        ans[2] = ans[1] * (pow2[k] - 1) % mod;
        for (int i = 3; i <= n; i++)
        {
            ll temp = pow2[k] - 1;
            ans[i] = (ans[i - 2] + pow2[k] *(power_mod(temp, i - 2)*(pow2[k] - 2) % mod)) % mod;
        }
        printf("%lld\n", ans[n]);
    }
}