contesthunter CH Round #64

http://www.contesthunter.org/contest/CH Round %2364 - MFOI杯水题欢乐赛 day1/Solve

Solve

CH Round #64 - MFOI杯水题欢乐赛 day1

题目描述

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

$Y_i = sum_{j=0}^{n-1}X_j imes f(ioplus 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	所有 Ai 都相同
5	<= 105	<= 109	所有 Ai 都相同
6,7,8,9,10	<= 105	<= 109	无

分析：

方法1，

　　可以先预处理W[j][0/1] 表示第j位是0/1的ｉ的ｉ的Xi值和，然后对于每位i，根据其二进制表示来累加答案即可。

　　时间复杂度O(n log n) , 可以拿下全部测试点。

方法2.

考虑把n增加为2的幂，并令新增加的数字为0.

然后先把n == 2时转移矩阵写出来：

0	1
1	0

可以发现矩阵大概是这样的；

A	A + T
A + T	A

其中A的边长为2的幂，T为全1矩阵。

如果对于所有的边长为2的幂的矩阵，都能像这样分解的话，那么是不是就可以分治了？

首先，对于2 * 2 的矩阵来说，很显然是满足条件的。

假设对于2^k * 2 ^k的矩阵来说是满足条件的，那么考虑2 ^(k + 1) * 2 ^(k + 1)的矩阵，其左上角就是原来的2^k * 2 ^k的那个矩阵，设为A，显然对于所有的0 <= i < 2^k和0 <=j < 2 ^k,都有：

f((i+2k)⊕j)=f(i⊕j)+1

是不是说明其左上角的矩阵等于A + T ?

同理：右上角和右下角也是满足条件的。

于是就可以分治的去做了。

时间复杂度：O(n log n)，可以拿下所有测试点。

AC代码：

代码很严谨，包括每个字符。。。orz

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 #define N 100000 + 5
10 #define Mod 1000000007
11 
12 int n, W[21][2];
13 
14 inline int getint()
15 {
16     char ch = '
';
17     for (; ch != '-' && (ch > '9' || ch < '0'); ch = getchar()) ;
18     int f = ch == '-' ? -1 : 1;
19     int res = ch == '-' ? 0 : ch - '0';
20     for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
21         res = (res << 3) + (res << 1) + ch - '0';
22     return res * f;
23 }
24 
25 inline int Inc(int a, int b)
26 {
27     return a + b - (a + b >= Mod ? Mod : 0);
28 }
29 
30 int main()
31 {
32     //#ifndef ONLINE_JUDGE
33    //     freopen("solve.in", "r", stdin);
34     //    freopen("solve.out", "w", stdout);
35    // #endif
36     
37     n = getint();
38     int d = (int) log2(n);
39     for (int i = 0; i < n; i ++)
40     {
41         int t = getint();
42         for (int j = 0; j <= d; j ++)
43             W[j][((i >> j) & 1)] = Inc(W[j][((i >> j) & 1)], t);
44     }
45     for (int i = 0; i < n; i ++)
46     {
47         int res = 0;
48         for (int j = 0; j <= d; j ++)
49             res = Inc(res, W[j][((i >> j) + 1) & 1]);
50         printf("%d%c", res, (i == n - 1) ? '
' : ' ');
51     }
52 
53    // #ifndef ONLINE_JUDGE
54    //     fclose(stdin);
55    //     fclose(stdout);
56    // #endif
57     return 0;
58 }

View Code