Codeforces Round #737 (Div. 2)C. Moamen and XOR(组合数学)

题目大意：
n个数，每个数小于\(2^k\)，求满足下列条件的方案数。

题解： 好蠢的题解。。。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+9;
const int mod=1e9+7;

int t;
int f[N];

int add(int x,int y)
{
	return (x%mod+y%mod)%mod;
}

int ksm(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)
		{
			res=1ll*res*x%mod; 
		}
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
}

void pre()
{
	f[0]=1;
	for(int i=1;i<=2e5;i++) f[i]=f[i-1]*2%mod;
} 

int main()
{
	pre();
	scanf("%d",&t);
	while(t--)
	{
		int ans=0;
		int n,k;
		scanf("%d%d",&n,&k);
		if(n&1)
		{
			ans=add(ans,ksm(1+f[n-1],k)); 
		}else
		{
			for(int i=1;i<=k;i++)
			{
				ans=add(ans,1ll*ksm(f[n],i-1)*ksm(f[n-1]-1,k-i)%mod);
			}
			ans=add(ans,ksm(f[n-1]-1,k));
		}
		cout<<ans<<endl;
	}
	return 0;
}

Codeforces Round #737 (Div. 2)C. Moamen and XOR(组合数学)

原文：https://www.cnblogs.com/zzyh/p/15253037.html