题目描述(和起床困难综合症思路类似)
C. Moamen and XOR
使得a1 & a2 & a3 & .. an >= a1 ^ a2 ^ a3 ^ .. ^ an ,其中每个a[i] < 2 ^ k,问这样的数组有多少个
思路:(可以发现位运算只会改变当前这一位)
只计算当前这一位全部进行操纵。
&:全1为1 有0为0
^:异为1, 同为0
假设n为奇数
$ C_{0}^{n} + C_{1}^{n} + C_{2}^{n} + C_{3}^{n} + … + C{n - 1}^{n} + C{n}^{n} = (1 + 1) ^ {n}$
$ C_{0}^{n} - C_{1}^{n} + C_{2}^{n} - C_{3}^{n} + … + C{n - 1}^{n} - C{n}^{n} = (1 - 1) ^ {n}$
两式子相加 $C_{0}^{n} + C_{2}^{n} + .. + C_{n}^{n - 1} = 2 ^{n - 1} $
可以求出 取偶数 还是奇数的组合数之和 那么如果为偶数 同理
可以发现 偶数个1进行异或为0,奇数个1进行异或为0, 当前这一位但凡有1个0,那么整体&后当前位一定为0
所以要分奇偶来讨论 左边(&) 右边为(^)
可以发现当n为奇数的时候,左右两边只有相等的情况
当n为偶数的时候,如果左边为1(所有的当前位都为1) 那么右边位0 出现了大于的情况
那么一旦出现了大于的情况,后面的随意放就行。
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
const ll mod = 1e9 + 7;
ll ksm(ll base, ll power)
{
ll res = 1;
while(power)
{
if(power & 1)
res = res * base % mod;
base = base * base % mod;
power >>= 1;
}
return res % mod;
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
ll n , k;
scanf("%lld %lld", &n, &k);
if(n % 2)
printf("%lld\n", ksm(ksm(2, n - 1) + 1, k) % mod);
else
{
ll res = 0;
for(int i = 1 ; i <= k ; i ++)
res += ksm(ksm(2, n - 1) - 1, i - 1) * ksm(ksm(2, n), k - i) % mod, res %= mod;
res += ksm(ksm(2, n - 1) - 1, k) % mod;
printf("%lld\n", res % mod);
}
}
return 0;
}