知识点
要考NOIP了。
NOIP一共要考k个知识点,考虑所有知识点的子集,共有n=2k个。
输入长度为n的数组a[i],下标从0开始,a[i]表示恰好掌握知识点集合i的人数。
其中i是一个子集,如果i的二进制第j位是1,那么表示这个集合包含知识点j,如果是0,表示不包含。
比如当k=6时,集合25的二进制是011001,从右向左,分别是第1,2,3,4,5,6个知识点
所以25包含知识点1,4,5,不包含知识点2,3,6。
假设NOIP会考察知识点集合i,B君希望知道有多少人掌握的知识点集合,包含考察的知识点集合i。
对于每个知识点集合i,B君都想知道答案。
输入描述
第一行一个整数n,保证是2的次幂。
接下来n行n个整数,表示a[i]。
输出描述
输出共n行,其中第i(0<=i<n)行表示i的答案。
样例输入
8
128
64
32
16
8
4
2
1
样例输出
255
85
51
17
15
5
3
1
样例解释
i=0的答案 a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
i=1的答案 a[1] + a[3] + a[5] + a[7]
i=2的答案 a[2] + a[3] + a[6] + a[7]
i=3的答案 a[3] + a[7]
i=4的答案 a[4] + a[5] + a[6] + a[7]
i=5的答案 a[5] + a[7]
i=6的答案 a[6] + a[7]
i=7的答案 a[7]
数据规模与约定
对于100%的数据,满足1<=n<=220,0<=a[i]<=1000
对于30%的数据,满足1<=n<=210
对于70%的数据,满足1<=n<=215