CF1557C

题目

source

题解

按位计算贡献，(dp[i])代表前(i)位的答案。第(i)位的贡献如下：

• 当(n)​为偶数时，如果第(i)位​全为1，那么前(i-1)​位可以随便取；
• 当(n)为奇数时，第(i)位不能全为1；
• 如果第(i)位不全为1，则第(i)位只能有偶数个1，贡献为((2^{n-1}-[n m is even])cdot dp[i-1])。

由于1的个数的奇偶是等概率的，所以(k)位二进制数奇数个1和偶数个1的数的个数相等，均为(2^{k-1})。

直接O(n)递推即可。

#include <bits/stdc++.h>
 
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;
 
using namespace std;
/*-----------------------------------------------------------------*/
 
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
 
const int N = 3e5 + 10;
const int M = 1e9 + 7;
const double eps = 1e-5;
 
ll pw[N];
ll dp[N];
 
inline ll qpow(ll a, ll b, ll m) {
    ll res = 1;
    while(b) {
        if(b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b = b >> 1;
    }
    return res;
}
 
int main() {
    IOS;
    pw[0] = 1;
    for(int i = 1; i < N; i++) pw[i] = pw[i - 1] * 2 % M;
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        dp[0] = 1;
        if(!(n % 2)) {
            for(int i = 1; i <= k; i++) {
                dp[i] = (qpow(pw[i - 1], n, M) + (pw[n - 1] - 1) * dp[i - 1] % M) % M;
            }
        } else {
            for(int i = 1; i <= k; i++) {
                dp[i] = (pw[n - 1] + 1) * dp[i - 1] % M;
            }
        }
        cout << dp[k] << endl;
 
    }
}