牛客ACM赛 B [小a的旅行计划 ]

链接 B 小a的旅行计划

把\(n\)个数中选任意数分成\(a,b\)两个集合，集合无区别，要求不包含且有交，求方案数。\(n\leq 10^{13}\)
首先讨论\(a,b\)并集是否为全集：
若是全集，那答案即为\(S(n,3)*3\)，也就是\(n\)个有区别的小球放在\(3\)个无区别盒子内，然后枚举三个盒子哪一个是交集。
若不是，则答案为\(S(n,4)*C(4,2)*2\)，也就是\(n\)个有区别的小球放在\(4\)个无区别盒子内，然后枚举哪两个是补集和交集，两个可以换。
答案就是两个加起来，\(S(n,4)\)这么算：

\[S(n,4)=\frac {2^{n-1}-3^{n-1}+\frac {4^{n-1}-1}{3}}{2}
\]

\(S(n,3)\)为：

\[\frac {3^{n-1}+1}{2}-2^{n-1}
\]

复杂度\(O(logn)\)

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=100001;

const int mod=1e8+7;

ll n,ans,res,inv2,inv3;

int gi(){

	R x=0,k=1;char c=getchar();

	while((c<'0'||c>'9')&&c!='-')c=getchar();

	if(c=='-')k=-1,c=getchar();

	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*k;

}

ll Qpow(ll x,ll y){

	ll ans=1,bas=x;

	while(y){

		if(y&1)ans=ans*bas%mod;

		bas=bas*bas%mod,y>>=1;

	}return ans;

}

int main(){

	cin>>n,inv2=Qpow(2,mod-2),inv3=Qpow(3,mod-2);

	ans=((inv2*(Qpow(3,n-1)+1)%mod-Qpow(2,n-1)+mod)%mod*3)%mod;

	res=(Qpow(4,n-1)-Qpow(3,n-1)+mod)%mod;

	res=(res+mod-(Qpow(4,n-1)-Qpow(2,n-1)))%mod;

	res=(res+inv3*(Qpow(4,n-1)-1)%mod);

	res=res*inv2%mod;

	cout<<(ans+res*12%mod)%mod<<endl;

	return 0;

}

巴特西

牛客ACM赛 B [小a的旅行计划 ]

链接 B 小a的旅行计划

最新文章

热门文章