codechef Count Relations(组合数 二项式定理)
2018-09-10 00:58:15来源:博客园 阅读 ()
题意
求有多少元素属于$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; } /* */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:CSP201612-2:工资计算
- CodeForces Gym 100213F Counterfeit Money 2020-02-13
- CountingSort(计数排序)原理及C++代码实现 2020-01-14
- 【题解】CF161B Discounts 2019-11-11
- constexpr函数"QAlgorithmsPrivate::qt_builtin_po 2019-04-30
- 1004 Counting Leaves (30 分)(树的遍历) 2018-12-09
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash