小红的相等数组

#include <iostream>
using namespace std;

int main() {
    int n, k, mod = 1e9 + 7;
    std::cin >> n >> k;

    auto ksm = [&](int x, int y) -> int {
        if (y < 0) return 0;
        int ans = 1;
        while (y) {
            if (y & 1) ans = 1ll* ans * x % mod;
            x = 1ll* x * x % mod;
            y >>= 1;
        }
        return ans;
    };

    if (n & 1) {
        // 全1 + 偶数1，每位独立。因为当全1时，&和^都是1，偶数1，那么&和^都是0，这样就是都是的大小
        // 2^n是所有的种类，所以偶数1为2^{n-1}
        std::cout << ksm(ksm(2, n-1)+1, k) << std::endl;
        return 0;
    }

    // n为偶数时，并不是独立的，因为全为1时，&是1，^为0，那么此时后面位都可以乱选也是符合条件的；那就枚举
    int ans = 0;
    for (int i = 1; i <= k; i ++) {
        int res = 1ll * ksm(ksm(2, n), i - 1) * ksm(ksm(2, n - 1) - 1, k - i) % mod;
        ans = (ans + res) % mod;
    }
    std::cout << (ans + ksm(ksm(2, n - 1) - 1, k)) % mod << std::endl;

}