codechef Count Relations(组合数 二项式定理)

题意

求有多少元素属于$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的交集不等于空集}

sol

神仙题啊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;
}
/*
*/