CodeChef - COUNTREL Count Relations

539 浏览 0 回复 2020-01-21

蒟蒟独行

+关注

题目
题意： $x$ 和 $y$ 为两个只包含 $1... N$ 中数的集合，要求：在 $x$ 和 $y$ 不为另一个的子集的情况下，分别求：
$1. x \cap y = \emptyset$
$2. x \cap y \neq \emptyset$
的个数， $(x, y)$ 与 $(y, x)$ 算一组，所以方案数要除以 $2$
这可能是我唯一想出过的组合计数的问题吧
中间要用多次二项式定理，但只要知道公式应该就能化简出来了
#####1:
随便选 $i (0 < i < n)$ 个点，为集合 $x$ ，剩下部分只要不全为空，随便填，为集合 $y$
方案数为： $[Σ_{i = 1}^{n - 1} C_{n}^{i} \cdot (2^{n - i} - 1)] / 2 = (3^{n} - 2^{n + 1} + 1) / 2$
#####2:
随便选 $i (0 < i < n)$ 个点为公共部分，再在剩下部分中选 $j (0 < j < n - i)$ 个点，与公共部分一起并作 $x$ ，剩下部分随便填，与公共部分一起构成集合 $y$
方案数为：
$[Σ_{i - 1}^{n - 1} C_{n}^{i} Σ_{j = 1}^{n - i - 1} C_{n - i}^{j} (2^{n - i - j} - 1)] / 2 = (4^{n} - 3^{n + 1} + 3 \cdot 2^{n} + 1) / 2$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e8+7;
int T;ll n,inv;
ll pw(ll x,ll y){
	ll z=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1) z=z*x%M;
	return z;
}
int main(){
	scanf("%d",&T);
	inv=pw(2,M-2);
	while (T--){
		scanf("%lld",&n);
		printf("%lld %lld\n",(pw(3,n)-pw(2,n+1)+1+M)%M*inv%M,
		(pw(4,n)-pw(3,n+1)+pw(2,n)*3%M-1+M*2)%M*inv%M);
	}
}