HDU 3929 Big Coefficients（容斥+证明）

本文主要是介绍HDU 3929 Big Coefficients（容斥+证明），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

(1 + x)^n 的奇数项系数个数等于 2^(bitcount(n))，bitcount(x)为x有多少个1.

然后容斥

枚举每一项存在不存在，然后容斥加加减减即可

这题用二进制枚举会T，只能DFS

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 15;
typedef long long ll;int t, n;
ll a[N];int bitcount(ll x) {if (x == 0) return 0;return bitcount(x>>1) + (x&1);
}ll pow2[100];
ll ans;void dfs(int u, ll w, int s) {for (int i = u; i < n; i++) {ll ss = (w&a[i]);ans += pow2[bitcount(ss)] * s;dfs(i + 1, ss, s * -2);}
}int main() {pow2[0] = 1;int cas = 0;for (int i = 1; i < 60; i++) pow2[i] = pow2[i - 1] * 2;scanf("%d", &t);while (t--) {scanf("%d", &n);ans = 0;for (int i = 0; i < n; i++) scanf("%I64d", &a[i]);dfs(0, (1LL<<50) - 1, 1);printf("Case #%d: %I64d\n", ++cas, ans);}return 0;
}

这篇关于HDU 3929 Big Coefficients（容斥+证明）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---