求有多少元素属于$1 \sim N$的集合满足
R1 = {(x,y):x和y属于B,x不是y的子集,y不是x的子集,x和y的交集等于空集}
R2 = {(x,y):x和y属于B,x不是y的子集,y不是x的子集,x和y的交集不等于空集}
神仙题啊Orz
我整整推了两个小时才推出来
首先写暴力
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
//#define int long long
#define LL int
const int MAXN = 1001;
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int C[MAXN][MAXN], Po2[MAXN];
main() {
cin >> N;
Po2[0] = 1;
for(int i = 1; i <= 1000; i++) Po2[i] = 2 * Po2[i - 1];
C[0][0] = 1;
for(int i = 1; i <= 1000; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
int ans = 0;
for(int i = 1; i <= N - 1; i++) {
int now = C[N][i], sum = 0;
for(int j = 1; j <= N - i; j++) sum += C[N - i][j];
//ans += now * sum;
ans += now * (Po2[N - i] - 1);
}
cout << ans / 2 << " ";
ans = 0;
for(int i = 2; i <= N - 1; i++) {
int res1 = C[N][i], sum1 = 0;
for(int j = 1; j <= i - 1; j++) {
int res2 = C[i][j], sum2 = 0;
for(int k = 1; k <= N - i; k++) {
sum2 += C[N - i][k];
}
sum1 += res2 * sum2;
}
ans += res1 * sum1;
}
cout << ans / 2;
return 0;
}
/*
100 50 10000006
*/
然后一层一层展开即可
最后的答案为
第一问:
$$\frac{3^n + 1}{2} - 2^n$$'
第二问:
$$\frac{-3 * 3^n + 4^n - 1}{2} + 3 * 2^{n - 1}$$
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define LL int
const int MAXN = 1001, mod = 100000007, inv = 50000004;
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int C[MAXN][MAXN], Po2[MAXN], Po3[MAXN], Po4[MAXN];
int f(int a, int p) {
int base = 1;
while(p) {
if(p & 1) base = (base * a) % mod;
a = (a * a) % mod; p >>= 1;
}
return base % mod;
}
main() {
int T;
cin >> T;
while(T--) {
cin >> N;
/*Po2[0] = Po3[0] = Po4[0] = 1;
for(int i = 1; i <= 1000; i++) Po2[i] = 2 * Po2[i - 1], Po3[i] = 3 * Po3[i - 1], Po4[i] = 4 * Po4[i - 1];
int ans = (Po3[N] + 1) / 2 - Po2[N];
cout << ans << " ";
ans = 0;
ans = (-3 * Po3[N] + Po4[N] - 1) / 2;
ans += Po2[N - 1] * 3;
cout << ans; */
//cout << f(2, mod - 2) % mod;
int ans = ((f(3, N) + 1) * inv - f(2, N) + mod) % mod;
cout << ans << " ";
ans = ((-3 * f(3, N) + mod) % mod + f(4, N) - 1 + mod) * inv + f(2, N - 1) * 3 % mod;
ans %= mod;
cout << ans << endl;
}
return 0;
}
/*
*/