题意
求有多少元素属于$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; } /* */
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/608173.html