首页 > 其他 > 详细

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

时间:2021-09-11 21:43:55      阅读:2      评论:0      收藏:0      [点我收藏+]

题目大意:
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

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!