Codeforces Round #737 (Div. 2)-C

C. Moamen and XOR
题目链接

【题目大意】
给定n,k,要求统计出有多少个包含n个小于2^n的整数序列满足其与运算结果大于等于异或运算结果
【思路】
统计每一位贡献的答案
分成两类

1. 当n为奇数时，想满足条件，n个元素每一位最多只能与运算结果大于等于异或运算，即只能有偶数个1或者都为0或者都为1；每一位的贡献为C_n^0 +C_n^2...也就是2 ^ (n-1)，再加上全为1的情况，答案为（2 ^ (n-1)+1）^n
2. 当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;
}

Codeforces Round #737 (Div. 2)-C

原文：https://www.cnblogs.com/DonaKui/p/15126123.html