题解 | #小红的好数组#

因为只有四种组合能构成偶数的组合，并且是重复的，用0表示偶数，1表示奇数，每去掉一个奇数就需要补一个奇数，同理去偶数补偶数，所以实际上就是00000000000000，110110110110110，101101101101101这样的长度n的数组，算出有多少个奇数可以选择和有多少个偶数可以选择，最后快速幂计算一下pow(奇偶选择，有多少个奇偶数）相乘得到结果

#include <cmath>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

// 带有取模的快速幂；
ll mod_pow(ll a, ll b) {
    ll ret = 1;
    a %= mod;

    while (b > 0) {
        if (b % 2 == 1) {
            ret = (ret * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}

int main() {
    int n, k;
    cin >> n >> k;
    int count = n / 3;
    int tail = n % 3;
    // 多少种奇偶组合
    ll evenCount = k / 2;
    ll oddCount = evenCount + (k % 2);
    unordered_map<string, pair<ll, ll>> mp;

    // 构成连续3个数为偶的组合，{奇数个数，偶数个数}；
    int a = 0, b = 0;
    mp["000"] = { 0, count * 3 + tail }; // 全偶数
    a = tail == 2 ? 1 : 0;
    b = tail >= 1 ? 1 : 0;
    mp["011"] = { count * 2 + a, count + b }; // 一个偶数，两个奇数
    a = tail >= 1 ? 1 : 0;
    b = tail == 2 ? 1 : 0;
    mp["101"] = { count * 2 + a, count + b };
    a = tail >= 0 ? tail : 0;
    mp["110"] = { count * 2 + a, count };
    ll ans = 0;
    
    for (auto& iter : mp) {
        ll odd = iter.second.first;
        ll even = iter.second.second;
        // 快速幂
        ll tempa = mod_pow(oddCount, odd) % mod;
        ll tempb = mod_pow(evenCount, even) % mod;
        ans += (tempa * tempb) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}