题目描述
给定 n 和 X0,X1,...,Xn-1，求解 Y0,Y1,...,Yn-1，其中：
f(x) 等于把 x 写成二进制后 1 的个数，比如说：
f(0)=0 , f(1)=1 , f(4)=1 , f(7)=3
其中 表示二进制下的按位异或运算。
请依次输出 Y0,Y1,...,Yn-1 对 取模的结果。
输入格式
输入第一行为一个正整数 n
输入第二行为 n 个非负整数，第 i 个数表示 Xi-1
输出格式
输出仅一行 n 个非负整数，第 i 个数表示 Yi-1 对 取模的结果。
样例输入
3 1 1 1
样例输出
2 3 3
数据范围及约定
| 测试数据点 | n | Xi | 特殊性质 |
| 1 | <= 10 | <= 10 | 无 |
| 2 | <= 100 | <= 100 | 无 |
| 3 | <= 1000 | <= 1000 | 无 |
| 4 | = 65536 | <= 109 | 所有 Ai 都相同 |
| 5 | <= 105 | <= 109 | 所有 Ai 都相同 |
| 6,7,8,9,10 | <= 105 | <= 109 | 无 |
题解：
做预处理：使用一个w数组保存二进制第j位是0/1的所有Xi的和，然后对于每位i累加答案输出。
复杂度分析：由于每个Xi二进制表示的贡献为log2(n)，因此总的复杂度就是O(n log n)了。
代码：
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 1000000007
int n,w[21][2],tmp,ans,digit;
inline int Inc(int a,int b){
return a + b - (a + b >= mod ? mod : 0);
}
int main(){
scanf("%d",&n);
digit = (int)log2(n);
for(int i = 0;i < n; i++){
scanf("%d",&tmp);
for(int j = 0; j <= digit ; j++)
w[j][(i >> j) & 1] = Inc(w[j][(i >> j) & 1], tmp);
}
for(int i = 0; i < n; i++){
ans = 0;
for(int j = 0; j <= digit; j++)
ans = Inc(ans, w[j][((i >> j) + 1) & 1]);
printf("%d%c",ans,i == n - 1 ? '\n' : ' ');
}
return 0;
}
今天这场MFOI又被虐了TAT，貌似就只有这一题看懂了正解，其它题只好先屯着了；
评论 (0)
