ZOJ 3556 How Many Sets I （容斥）

本文主要是介绍ZOJ 3556 How Many Sets I （容斥），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题是个容斥。

总情况有2^(nk)中，但是其中包含了1个重复元素，2个，3个。。

用容斥，1个重复元素加上，2个减去，3个加上

这样推出公式为

C(n, 0)2^(nk) - C(n, 1)2^((n -1)k) + C(n, 2)2^((n - 2)k)......

==> (2^k - 1)^n 

快速幂取模计算即可

代码：

#include <cstdio>
#include <cstring>typedef long long ll;const int MOD = 1000000007;int pow_mod(int x, int k) {int ans = 1;while (k) {if (k&1) ans = (ll)ans * x % MOD;x = (ll)x * x % MOD;k >>= 1;}return ans;
}int n, k;int main() {while (~scanf("%d%d", &n, &k)) {printf("%d\n", pow_mod((pow_mod(2, k) - 1 + MOD) % MOD, n));}return 0;
}

这篇关于ZOJ 3556 How Many Sets I （容斥）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---