CodeChef - COUNTREL Count Relations

题目链接
给你一个长为 $N$N的 $1,2,3,....N$1,2,3,....N的序列,让你求出两种关系各个有多少可能；
$R_1$R1​，由于 $x,y$x,y互不是子集，且交集为空。我们可以这样考虑:先对 $x$x进行分析，假定 $x$x中有 $X$X个元素,因为空集是所有集合的子集，所以显然 $x$x必不能不取且不能取满 $N$N个,那么当 $x$x有 $X$X个元素时，就有
$C{(}_N^X\left)\right(1\le X\le n-1)$C(NX​)(1≤X≤n−1)种取值方案。
那么剩下的 $n-x$n−x个数字就要留给 $y$y，显然 $y$y集合中必然有元素，假定 $y$y中有 $Y$Y个元素，所以在当前情况下有
$C{(}_{N-X}^Y\left)，\right(1\le Y\le n-X)$C(N−XY​)，(1≤Y≤n−X)种取值.
那么综上所述，第一个问题的答案就有 ${\sum }_{X=1}^{N-1}\left(C{(}_N^X\right)\ast {\sum }_{Y=1}^{N-X}C{(}_{N-X}^Y\left)\right)$∑X=1N−1​(C(NX​)∗∑Y=1N−X​C(N−XY​)).
然后就是大力化简这个式子了。
先考虑 ${\sum }_{Y=1}^{N-X}C{(}_{N-X}^Y)$∑Y=1N−X​C(N−XY​)，由组合数的基本公式可知 ${\sum }_{Y=0}^{N-X}C{(}_{N-X}^Y)=2^{N-X}$∑Y=0N−X​C(N−XY​)=2N−X,那么 ${\sum }_{Y=1}^{N-X}C{(}_{N-X}^Y)=2^{N-x}-1$∑Y=1N−X​C(N−XY​)=2N−x−1;
那么上式可化简为
${\sum }_{X=1}^{N-1}C{(}_N^X)\ast (2^{N-X}-1)={\sum }_{X=1}^{N-1}C{(}_N^X)\ast 2^{N-X}-{\sum }_{X=1}^{N-1}C{(}_N^X)$∑X=1N−1​C(NX​)∗(2N−X−1)=∑X=1N−1​C(NX​)∗2N−X−∑X=1N−1​C(NX​)
易知 ${\sum }_{X=1}^{N-1}C{(}_N^X)=2^N-2$∑X=1N−1​C(NX​)=2N−2。
在考虑左半部分，由二项式定理可知 ${\sum }_{i=0}^{N}C{(}_N^i)a^i{b}^{N-i}=(a+b{)}^N$∑i=0N​C(Ni​)aibN−i=(a+b)N
那么左半部分可化简为 $(1+2{)}^N-C_N^0{2}^N-C_N^N{2}^0=3^N-2^N-1$(1+2)N−CN0​2N−CNN​20=3N−2N−1
即原式可化简为 $3^N-2^N-1-2^N+2=3^N-2^{N+1}+1$3N−2N−1−2N+2=3N−2N+1+1，由于 $x,y$x,y无序，所以除二即为第一部分最后答案。
第二部分：要求 $x,y$x,y有交集，那么我们可以先设交集的长度为 $i$i,那么剩下的部分就是 $x,y$x,y个站一些不空且不相交的部分，那么显然答案就是
${\sum }_{i=1}^{N-2}{\sum }_{j=1}^{n-i-1}C{(}_{N-i}^j\left){\sum }_{k=1}^{N-i-j}C{(}_{N-i-j}^k\right)$∑i=1N−2​∑j=1n−i−1​C(N−ij​)∑k=1N−i−j​C(N−i−jk​).
化简和上面一样，多用几次二项式定理就行了。
化简出来就是 $4^N-3^{N+1}-1+3\ast 2^N$4N−3N+1−1+3∗2N，同样答案除以2即可。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
const int mod=100000007;
LL Inv[N],Fac[N];
void P(){
	Fac[0]=1;
	for(int i=1;i<N;i++)Fac[i]=Fac[i-1]*i%mod;
	Inv[N-1]=powmod(Fac[N-1],mod-2,mod);
	for(int i=N-2;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%mod;
}
LL get(int l,int r){
	return Fac[l]*Inv[r]%mod*Inv[l-r]%mod;
}

LL n;
int main(){
	ios::sync_with_stdio(false);
	// P();
	int t;
	for(cin>>t;t;t--){
		cin>>n;
		cout<<(powmod(3,n,mod)-powmod(2,n+1,mod)%mod+1+2*mod)%mod*powmod(2,mod-2,mod)%mod<<' ';
		cout<<(powmod(4,n,mod)-powmod(3,n+1,mod)-1+3*powmod(2,n,mod)%mod+2*mod)%mod*powmod(2,mod-2,mod)%mod<<endl;
	}
	return 0;
}