• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

「NOIP2021模拟赛8.19 A」集合(set)题解

admin

11月 28, 2021

题目大意

「NOIP2021模拟赛8.19 A」集合(set)

给定一个包含(n)个元素的集合(S),请找出(k)个可以相等的子集(S_1,S_2,…,S_k)使得交集是空集,求满足条件的方案数

问题求解

我们依次考虑每个数包含在那些集合中,显然为了使所有集合相交为空集,它不能被所有集合都包含,其他的情况都是可以的,因此考虑每个数的方案数是(2^k-1),容易发现不同的数之间互不影响,所以答案就是((2^k-1)^n)

然后对于(n,k≤10^{63})我们可以考虑用高精度来处理,但如果不想写高精度的话可以考虑用欧拉定理来实现

[a^{varphi(n)}equiv1
]

所以我们在(n,k)读入时摸(varphi(n))也就是(mod-1)就好了

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=1e9+7;
LL n,k;
LL QSM(LL a,LL b){
	LL s=1,w=a;
	while(b){
		if(b&1)s=s*w%TT;
		w=w*w%TT;
		b>>=1;
	}
	return s;
}
LL read(){
	LL ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ret%=TT-1,ch=getchar();
	return ret*f;
}
int main(){
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	n=read();k=read();
	printf("%lld
",QSM((QSM(2,k)+TT-1)%TT,n));
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。