ACM模版

描述

题解

哎，这个题比赛时要是大胆的打表试试也许可以发现一些规律……看到数学公式推导题我就犯怵……这样子不好╮(╯﹏╰)╭不好。

刚拿到这个题时，我认为这个题是类似于斐波那契数列的矩阵求解那样，但是我矩阵好菜的，不会构造单位矩阵，故卒。后来发现这个题除了这种思路，还能找到一个规律，最后变成一个公式。前者方案是官方题解的解法，后者就是比较容易写的解法了……当然问题的关键是是否能找到规律，如果尝试打表一下，也许真的能够找到……

对了，先贴一下官方题解吧，给大家参考一下：

最后，给出一下最终公式：

ans=⎧⎩⎨⎪⎪2(2n−1)m−13,2(2n−1)m−1+13,n & 1 == 0n & 1 == 1

第一个解法代码稍微长一些，第二个就简单多了……

代码

#include <cstdio>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll QPow(ll x, ll n)
{
    ll ret = 1;
    for (; n; n >>= 1)
    {
        if (n & 1)
        {
            ret = ret * x % MOD;
        }
        x = x * x % MOD;
    }

    return ret;
}

ll inv(ll x)
{
    return QPow(x, MOD - 2);
}


ll n,m;
ll ans;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%lld", &n, &m);
        if (n & 1)
        {
            ans = (QPow(QPow(2, n) - 1, m - 1) * 2 % MOD + 1) * inv(3) % MOD;
        }
        else
        {
            ans = QPow(QPow(2, n) - 1, m - 1) * 2 % MOD * inv(3) % MOD;
        }

        printf("%lld\n", ans);
    }

    return 0;
}