hihoCoder 1549 或运算和

#1549 : 或运算和

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定N个数A1...AN (0 <= Ai < 220) 和一个正整数K，我们用Ans[i]表示有多少种从这N个数中选取K个数的方案，满足这K个数的或运算和正好为i。

你能对于每一个i(0 <= i < 220)都计算出Ans[i]的值吗？

为了简化输出，你只需要输出Σ(Ans[i] * i) 除以1000000007的余数。

输入

第一行一个数T(<=10)，表示数据组数

对于每一组数据：

第一行两个数N，K（1<=N<=100,000，K<=1000）

第二行N个数A1...AN (0 <= Ai < 220)

输出

一个数表示答案

样例输入

样例输出

//其实，若是理解了，很容易做出来

直接分析答案，

∑(ANS[i] * i ) = ∑(ANS[i] * (2^p1+2^p2+2^p3+...+2^px)) (Pi 为互不相同的自然数)

= 2⁰ * (Ans[0]+ANS[1]+...+ ANS[2²⁰-1])

+2¹ * (Ans[0]+ANS[1]+...+ ANS[2²⁰-1])

+...

+2¹⁹ * (Ans[0]+ANS[1]+...+ ANS[2²⁰-1])

然后，发现，(Ans[0]+ANS[1]+...+ ANS[2²⁰-1])这部分，代表的意思是，n 个数中选 k 个数或出 0 -- 2²⁰-1 的种数。选 k 个数不管如何，或出来肯定在 0 - 2²⁰-1 之中，所以 2ⁱ * (Ans[0]+ANS[1]+...+ ANS[2²⁰-1]) 就是 n 个数中，转二进制，第 i 位选 k 个或出 1 的种数，然后就简单的排列组合，求逆元，累加即可。

或者简单的撕拷，选 k 个数，组成了一种 i ，i 是由 (2^p1+2^p2+2^p3+...+2^px）组成，答案中就包含了这部分，所以，找到所有选 k 个数可以让 x (0-19)位变为 1 的种数，再乘以权值，即为答案，其实这就是算贡献，还得好好练啊！

 1 # include <cstdio>
 2 # include <cstring>
 3 # include <cstdlib>
 4 # include <iostream>
 5 # include <vector>
 6 # include <queue>
 7 # include <stack>
 8 # include <map>
 9 # include <bitset>
10 # include <set>
11 # include <cmath>
12 # include <algorithm>
13 using namespace std;
14 #define lowbit(x) ((x)&(-x))
15 #define pi acos(-1.0)
16 #define eps 1e-8
17 #define MOD 1000000007
18 #define INF 0x3f3f3f3f
19 #define LL long long
20 inline int Scan() {
21     int x=0,f=1; char ch=getchar();
22     while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
23     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
24     return x*f;
25 }
26 inline void Out(int a) {
27     if(a<0) {putchar('-'); a=-a;}
28     if(a>=10) Out(a/10);
29     putchar(a%10+'0');
30 }
31 #define MX 100005
32 //Code begin...
33 int n,k;
34 int a[MX];
35 
36 LL qk_mi(LL x,LL y)
37 {
38     LL res = 1;
39     while (y)
40     {
41         if (y&1) res = res*x%MOD;
42         x = x*x%MOD;
43         y/=2;
44     }
45     return res;
46 }
47 
48 LL C(LL x,LL y)// m   n
49 {
50     if (x>y) return 0LL;
51     LL res =1;
52     for (int i=1;i<=y;i++)
53         res = (res*i)%MOD;
54     LL mj = 1,mnj = 1;
55     for (int i=1;i<=x;i++)
56         mj = (mj*i)%MOD;
57     for (int i=1;i<=(y-x);i++)
58         mnj = (mnj*i)%MOD;
59     mj = qk_mi(mj,MOD-2); mnj = qk_mi(mnj,MOD-2);
60     res = (res*mj%MOD) * mnj %MOD;
61     return res;
62 }
63 
64 LL slove(int x,int y)
65 {
66     LL res = C(k,x+y);
67     res = (res +MOD -C(k,x))%MOD;
68     return res;
69 }
70 
71 int main()
72 {
73     int T=Scan();
74     while(T--)
75     {
76         n = Scan();k = Scan();
77         for (int i=0;i<n;i++)
78             a[i] = Scan();
79         LL ans = 0;
80         for (int i=0;i<20;i++)
81         {
82             int zero=0,one=0;
83             for (int j=0;j<n;j++)
84                 if ((a[j]>>i)&1) one++;
85                 else zero++;
86             ans = (ans + (1LL<<i)*slove(zero,one)%MOD )%MOD;
87         }
88         printf("%lld
",ans);
89     }
90     return 0;
91 }

View Code