首页 > 代码库 > ZOJ 3556 How Many Sets I 二项式+容斥
ZOJ 3556 How Many Sets I 二项式+容斥
n个元素的子集有2^n个 求从这些子集选出k个组成有序集 并且有序集的交集为空的方案数
总数为2^n^k 减去不符合的
不符合的为交集存在1个共同元素 存在2个共同元素....
2^n^k-C(n, 1)*2^(n-1)^k+C(n, 2)*2^(n-2)^k....
(2^k-1)^n
#include <cstdio> #include <cstring> using namespace std; typedef long long LL; //返回a^p mod n 快速幂 LL pow_mod(LL a, LL p, LL n) { LL ans = 1; while(p) { if(p&1) { ans *= a; ans %= n; } a *= a; a %= n; p >>= 1; } return ans; } int main() { LL n, m; while(scanf("%lld %lld", &n, &m) != EOF) { printf("%lld\n", pow_mod((pow_mod(2, m, 1000000007)-1), n, 1000000007)); } return 0; }
ZOJ 3556 How Many Sets I 二项式+容斥
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。