4
11
2015
0

MFOI D1T1 Solve

题目描述

给定 n 和 X0,X1,...,Xn-1,求解 Y0,Y1,...,Yn-1,其中:

$$Y_i = \sum_{j=0}^{n-1}X_j\times f(i\oplus j)$$

f(x) 等于把 x 写成二进制后 1 的个数,比如说:

f(0)=0 , f(1)=1 , f(4)=1 , f(7)=3

其中 $\oplus$ 表示二进制下的按位异或运算。

请依次输出 Y0,Y1,...,Yn-1 对 $10^9+7$ 取模的结果。

 

输入格式

输入第一行为一个正整数 n

输入第二行为 n 个非负整数,第 i 个数表示 Xi-1

输出格式

输出仅一行 n 个非负整数,第 i 个数表示 Yi-1 对 $10^9+7$ 取模的结果。

样例输入

3

1 1 1

样例输出

2 3 3

数据范围及约定

 

测试数据点 n Xi 特殊性质
1 <= 10 <= 10
2 <= 100 <= 100
3 <= 1000 <= 1000
4 = 65536 <= 109 所有 A都相同
5 <= 105 <= 109 所有 A都相同
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,貌似就只有这一题看懂了正解,其它题只好先屯着了;

Category: 其他题库 | Tags: | Read Count: 602

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com