题目大意：给定一个n，和一个k。代表着有n个数，其中每个数的值都比 2^k 小，并且这n个数组都以下满足不等式
求有多少种符合题意的方案.
分析：对于一个n位，每一位数字t不大于2^k的情况
方案为大于等于，所以我们拆开来分析：我们只考虑将t在二进制形势下考虑，考虑k的某一位的连续异或和连续与的操作结果：
1.AND与XOR相等的情况
这种情况当且仅当n为奇数时，而且每一位都取1才成立
此情况只要有偶数个1便成立
2.AND与XOR不相等的情况
此时一定有此位上的所有数字都是１,因此只有在偶数的情况下才能成立
解题步骤
按照奇偶性继续分类整理得到：
1.当n为奇数的时候
AND=XOR=1和AND=XOR=0两种情况,因此对于总的情况数为，每一位的情况数的k次幂（因为小于2^k，所以总共k位进行考虑）
2.当n为偶数的时候
共AND=XOR=0和AND>XOR两种情况
1)AND=XOR 偶数个1的情况，其中要把全部是1的情况去掉，因此此时并不相等
2)AND>XOR 考虑循环，当考虑第i位时，第i位全部是1，因此前i为应该相等，直接套用上面的公式，然后后i位可以任意取，根据乘法公式乘起来便是最终答案
因此偶数情况便是上述两者相加而得
附上AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
typedef long long LL;
template <typename T>void read(T &x){x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}x*=f;return;}
template <typename T>void write(T x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');return;}
const int mod=1e9+7;
int T;
int n,k;
int fpower(int a,int b,int mod){
int res=1;
for(;b;b>>=1){
if(b&1) res=(LL)res%mod*a%mod;
a=(LL)a*a%mod;
}
return res;
}
int mo(int x){
return ((LL)x%mod+mod)%mod;
}
int main(){
read(T);
while(T--){
read(n),read(k);
int ans=0;
if(n&1) ans=fpower(fpower(2,n-1,mod)+1,k,mod);
else{
int power2=fpower(2,n-1,mod);
int ppower2=fpower(2,n,mod);
for(int i=1;i<=k;i++){
ans=mo((LL)ans+(LL)fpower(ppower2,(k-i),mod)*fpower(mo(power2-1),i-1,mod)%mod);
}
ans=mo(((LL)ans+fpower(power2-1,k,mod)%mod)%mod);
}
write(ans);
puts("");
}
return 0;
}
|