求满足条件的集合方案数量
- A, B的交集不能为空集
- 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;
}
