OIES公式合集

求满足条件的集合方案数量

1. A, B的交集不能为空集
2. A, B不能相互包含(A=B也属于相互包含)

注意：在这里我们认为(A,B)是无序的，即(A,B)和(B,A)是同一种方案
求总方案的数量

{0, 0, 0, 3, 30, 195, 1050, 5103, 23310, 102315, 437250, 1834503, 7597590, 31175235, 127067850, 515396703, 2083011870, 8396420955, 33779000850, 135696347703, 544527210150, 2183335871475, 8749027724250, 35043169903503, 140313869216430, 561679070838795}

公式 :

代码 :

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 100000007;


ll ppow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll inv(ll a, ll mod) {
    return ppow(a, mod-2);
}

int main() {
    ll n;
    scanf("%lld", &n);
    n += 1;
    ll ans;
    ll inv_8 = inv(8, mod);
    ans = (ppow(4,n)%mod+(-4*ppow(3,n)+mod)%mod+6*ppow(2,n)%mod-4 + mod) %mod * inv_8 % mod;
    printf("%lld\n", ans%mod);
    return 0;
}

高度为n的大正三角形中 正三角形的个数

[图片上传失败...(image-7fea76-1542678378768)]

{0, 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410}

公式：

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

ll ppow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll inv(ll a, ll mod) {
    return ppow(a, mod-2);
}

int main() {
    int T;
    ll n, ans;
    ll inv_24 = inv(24, mod);
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        ans = n * (n + 1) % mod * (n + 2) % mod * (n + 3) % mod * inv_24 % mod;
        printf("%lld\n", ans % mod);
    }
    return 0;
}