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）
由此可以得出
当前有效情况数：
最后利用递推公式快速求组合数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 ;
}
伪·优化