hihocoder 1549 或运算和

题目

链接 http://www.hihocoder.com/problemset/problem/1549

给定 $n$ 个数字 $a_1,…,a_n(0 \leq a_i \leq 2^{20})$ 和一个正整数 $K$,$ans_i$ 表示从这 $n$ 个数中取 $k$ 个数的方案数,$i$ 为这个 k 个数的或运算和,求 $\sum ans_i * i$ 的值。

分析

一开始算的时候一直觉得是个数位 dp 值,想用 dp[i][j][2] 表示使用 i 个数,使得第 j 位为 0 或 1 的方案数,那么 dp[i+1][j][1] = (dp[i-t][j][0] * dp[t]j[1] + dp[i-t][j][1] * dp[t]j[0] + dp[i-t][j][1] * dp[t][j][1]),但是这么做必然会出现重复选用的问题,然后越想越复杂。

赛后看了下学弟的解,然后就明白怎么做了。一开始按每一位去算贡献的思路是对的,不过算法上不需要 dp。

对于任意位 $i$ 而言,要从 $n$ 个数里选 $k$ 个数使得这一位为 $0$,那么只有这 $k$ 个数在第 $i$ 位上都为 $0$ 才行。反之需要和在第 $i$ 位为 1,那么就减掉使得和为 0 的这种情况就行了。因此,我们预先统计所有数在第 $i$ 位为 1 出现的次数,用 $cnt_i$ 表示。那么使得第 $i$ 位为 1 总共的方案数为:

$$f_i=\binom{n}{k}-\binom{n-cnt_i}{k}$$

即从所有 $n$ 个数中选 $k$ 个数的方案数减去从第 $i$ 位的不为 1 的 $n-cnt_i$ 个数选 $k$ 个数的方案数即为使得这一位为 1 的方案数总和。那么最后把每一位换算成十进制,最后得到解即为:

$$ans=f_i * i * 2^i$$

其中需要运算组合数取模,不需要用卢卡斯定理,可以直接用公式

$$\binom{n}{k}=\frac{n!}{k!*(n-k)!}$$

其中分子部分直接用 $O(n)$ 预处理出所有的数的阶乘,分母则需要求出所有数阶乘的逆元,同样可以使用 $O(n)$ 进行预处理。最快速的方法就简单使用扩展欧几里得,即

$$invi \bmod p=inv{p \bmod i} * (p - p/i) \bmod p$$

或者用费马小定理

$$inv_i \bmod p = pow(i, p - 2) \bmod p$$

对每个数求好逆元以后再用 $O(n)$ 递推一下即可。

最后就是在模运算时注意加减乘除对应的操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100010;
const int mod = 1000000007;
#define ll long long
ll fac[maxn], inv[maxn];
int cnt[25];
void init() {
fac[0] = inv[0] = 1;
for(int i = 1; i < maxn; i++) {
fac[i] = fac[i - 1] * i % mod;
}
inv[1] = 1;
for(int i = 2; i < maxn; i++) {
inv[i] = inv[mod % i] * (mod - mod/i) % mod;
}
for(int i = 2; i < maxn; i++) {
inv[i] = inv[i] * inv[i-1] % mod;
}
}
ll C(int n, int k) {
return k > n ? 0 : fac[n] * inv[k] % mod * inv[n-k] % mod;
}
int main() {
int t, n, k;
init();
scanf("%d", &t);
while(t--) {
while(~scanf("%d%d", &n, &k)) {
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
for(int j = 0; j < 20; j++) {
cnt[j] += (x >> j) & 1;
}
}
ll b = 1, ans = 0;
for(int j = 0; j < 20; j++) {
ans = (ans + (C(n, k) - C(n - cnt[j], k) + mod) % mod * b % mod) % mod;
b *= 2;
}
printf("%lld\n", ans);
}
}
}