CodeChef - COUNTREL Count Relations

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