题目E

小红定义一个数组是好数组，当且仅当所有长度为 3 的连续子数组的元素和为偶数。 现在小红希望你求出，长度为n，且所有元素均为不超过k的正整数的好数组数量。由于答案可能过大，请对10^9+7取模。

解题思路

看到数据范围，应该是有关数学的知识，分类讨论，虽然在比赛中讨论出来所有情况，但是没有写出来，还得练！！！！ 总共有四种情况：（用0表示偶数，1表示奇数）

1.000 000 000 000

2.011 011 011 011

3.101 101 101 101

4.110 110 110 110

每一个偶数位上有k/2个选择，有n1个偶数位，方案数是:n1^(k/2)，这里用到了快速幂的知识，同理得奇数位的方案数：n2^(k - k/2)，两个相乘即可得到：总方案数。

下面来根据分类讨论的结果写出代码即可。

代码

// 这种题目就是组合数学
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

typedef long long ll;
ll n, k;
int mod = 1e9 + 7;

ll quickpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if(b & 1)  res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
// 000 000 000 000
// 011 011 011 011
// 101 101 101 101
// 110 110 110 110

int main()
{
    cin >> n >> k;
    int k2 = k / 2, k1 = k - k2;
    ll tmp1 = quickpow(k2, n) % mod;
    ll tmp2 = (quickpow(k2, n / 3) * quickpow(k1, n - n / 3)) % mod;
    ll tmp3 = (quickpow(k2, (n + 1) / 3) * quickpow(k1, n - (n + 1) / 3)) % mod;
    ll tmp4 = (quickpow(k2, (n + 2) / 3) * quickpow(k1, n - (n + 2) / 3)) % mod;
    cout << (tmp1 + tmp2 + tmp3 + tmp4) % mod << endl;
    return 0;
}