FJNU 1153 Fat Brother And XOR(胖哥与异或)

FJNU 1153 Fat Brother And XOR(胖哥与异或)

Time Limit: 1000MS   Memory Limit: 257792K

【Description】

【题目描述】

Fat brother had master ACM, recently he began to study the operation of XOR (the operation “^”). He thought of a very interesting question: select arbitrary k positive integers from the n positive integers, then XOR the selected k digital, sum all cases of XOR. Now he wants to quickly calculate the results. Maybe the results will be great, just modulo 20162333.

For example, 3 integers: 1 2 3, select arbitrary 2 positive integers, the all cases:

{1,2}, {2, 3}, {1, 3}. So the results is {(1 ^ 2) + (2 ^ 3) + (1 ^ 3)} %20162333

胖哥是个ACM大牛,最近他在学习异或操作(运算符为“^”)。他想到了个有趣的问题:从n个正整数中任选k个,然后对这k个数异或,对所有异或的结果求和。现在他想快速计算结果。最终结果可能很大,于是模20162333。

例如,3个整数:1 2 3,选择任意2个正整数,所有情况为:

{1,2}, {2, 3}, {1, 3}。因此结果为{(1 ^ 2) + (2 ^ 3) + (1 ^ 3)} %20162333

【Input】

【输入】

There are multiple test cases. The first line of input contains an integer T (T <= 20) indicating the number of test cases. For each test case:

The first line contains two integer n, k (1 <= k <= n <= 1000)

The second line contains n integer ai (1 <= ai <= 1000000000)

多组测试用例。

第一行是一个整数T(T <= 20)表示测试用例的数量。对于每个测试用例:

第一行有两个整数,k(1 <= k <= n <= 1000)

第二行有n个整数ai(1 <= ai <= 1000000000)

【Output】

【输出】

For each test case, output the sum % 20162333

对于每个测试用例,输出和%20162333

【Sample Input - 输入样例】

【Sample Output - 输出样例】

2

3 2

1 2 3

6 2

6 6 6 6 6 6

6

0

【Hint】

【提示】

The

first sample test case: (1 ^ 2) + (2 ^ 3) + (1 ^ 3) = 6

The

second sample test case: (6 ^ 6) * 15 = 0

第一个样例:

(1 ^ 2) + (2 ^ 3) + (1 ^ 3) = 6

第二个样例:

(6 ^ 6) * 15 = 0

【题解】

这道题需要以二进制的观点来看待每个ai

举个例子:

Xai表示二进制的下ai的第X位(为方便表示从0开始)

(a1 ^ a2) + (a2 ^ a3) + (a1 ^ a3)

=[(0a1 ^ 0a2) + (0a2 ^ 0a3) + (0a1 ^ 0a3)]*20 +

[(1a1 ^ 1a2) + (1a2 ^ 1a3) + (1a1 ^ 1a3)]*21 +

[(2a1 ^ 2a2) + (2a2 ^ 2a3) + (2a1 ^ 2a3)]*22 +

…………………………………………………………………………… +

[(Xa1 ^ Xa2) + (Xa2 ^ Xa3) + (Xa1 ^ Xa3)]*2X

此时只剩0和1了

我们可以很轻易地知道:0 ^ 0 = 0, 1 ^ 0 = 1, 1 ^ 1 = 0

当然了,a ^ b = b ^ a

所以除了1 ^ 0之外,其他结果为0的情况都是无用的。

因此,题目转换为:求二进制下,1 ^ 0 这种情况出现的次数。

统计ai中二进制第X位出现几次1,保存到bit[x]

第X位提供的1 = 2X * 有效情况数

有效情况数就是由bit[X]个1与 n-bit[X]个0组合出来的

并且只有取奇数个1的时候,异或的结果才能为1(1 ^ 1 = 0)

由此可以得出

当前有效情况数:FJNU 1153 Fat Brother And XOR(胖哥与异或)

最后利用递推公式快速求组合数c(n,m)=c(n-1,m-1)+c(n-1,m)

(当然你把这个公式当成杨辉三角也是可以的:))

【代码 C++】

 #include<cstdio>
#include <cstring>
#define mx 1005
#define mod 20162333
int main(){
int t, n, k, i, j, w, opt, bit[], c[mx][mx];
for (i = ; i < mx; ++i){
for (c[i][] = c[i][i] = j = ; j < i; ++j)
c[i][j] = (c[i - ][j] + c[i - ][j - ]) % mod;
}
while (~scanf("%d", &t)){
while (t--){
memset(bit, , sizeof(bit));
scanf("%d%d", &n, &k);
for (i = ; i < n; ++i){
scanf("%d", &j);
for (w = ; j; j >>= ) bit[w++] += j & ;
}
for (i = opt = ; i < ; ++i){
for (j = ; j <= k; j += ){
opt += (1LL << i) *c[bit[i]][j] % mod*c[n - bit[i]][k - j] % mod;
opt %= mod;
}
}
printf("%d\n", opt);
}
}
return ;
}
 #include<cstdio>
#include <cstring>
#define mx 1005
#define mod 20162333
int read_int(){
int add = getchar() - '';
int a = getchar();
while (a >= '' && a <= '') add = add * + a - '', a = getchar();
return add;
}
int main(){
int t, n, k, i, j, w, opt, bit[], *c[mx];
for (i = ; i < mx; ++i){
c[i] = new int[i + ];
for (c[i][] = c[i][i] = j = ; j < i; ++j)
c[i][j] = (c[i - ][j] + c[i - ][j - ]) % mod;
}
while (t = read_int(), t>){
while (t--){
memset(bit, , sizeof(bit));
n = read_int(); k = read_int();
for (i = ; i < n; ++i){
for (w = , j = read_int(); j; j >>= ) bit[w++] += j & ;
}
for (i = opt = ; i < ; ++i){
for (j = ; j <= k; j += ){
if (bit[i] < j || n - bit[i] < k - j) continue;
opt += (1LL << i) *c[bit[i]][j] % mod*c[n - bit[i]][k - j] % mod;
opt %= mod;
}
}
printf("%d\n", opt);
}
}
return ;
}

伪·优化

上一篇:Pig系统分析(6)-从Physical Plan到MR Plan再到Hadoop Job


下一篇:[原创,分享]DbHelper 续