C. Moamen and XOR
题目链接
【题目大意】
给定n,k,要求统计出有多少个包含n个小于2^n的整数序列满足其与运算结果大于等于异或运算结果
【思路】
统计每一位贡献的答案
分成两类
- 当n为奇数时，想满足条件，n个元素每一位最多只能与运算结果大于等于异或运算，即只能有偶数个1或者都为0或者都为1；每一位的贡献为C_n^0 +C_n^2...也就是2 ^ (n-1)，再加上全为1的情况，答案为（2 ^ (n-1)+1）^n
- 当n为偶数时，答案分成两块，从每个元素从2进制最高位到最低来统计答案，除了全为1的情况n个元素每一位最多只能与运算结果大于等于异或运算，所以我们先统计除了全为1的情况，（2 ^ (n-1)-1）n，这里2(n-1)-1是因为n是偶数，我们统计偶数个1时包含了全为1的情况，然后再从高到底考虑每一位，如果当前位数全为1，即或运算为1，异或为0，那么后面的二进制数怎么取都满足，答案加上prod*Power(Power(2,i),n),i代表当前位之后的位数，prod位当前位之前的情况数，Power为快速幂运算；
【代码如下】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int Power(int x,int y){
int r=1;
while(y){
if(y&1)r=1ll*r*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return r;
}
int main(){
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
// cout<<Power(Power(2,0),n)<<endl;
int prod=1,ans=0;
for(int i=k-1;i>=0;i--){
if(n%2==0)ans=(ans+1ll*prod*Power(Power(2,i),n))%mod;
int u=0;
u=Power(2,n-1);
if(n%2==0)u=(u-1+mod)%mod;
if(n&1)u=(u+1)%mod;
prod=1ll*prod*u%mod;
}
ans=(ans+prod)%mod;
cout<<ans<<‘\n‘;
}
return 0;
}