【题面】
题目描述
对于两个非负整数 \(a,b\) ，如果 \(a∣b=b\) ，则称 \(a\) 是 \(b\) 的子集，记作 \(a⊆b\) 。其中 \(∣\) 表示按“位或”运算。
给定一个长度为 \(2^p\) 的序列 \({a_0},{a_1},{\dots},{a_{{2^p}-1}}\)。
我们定义函数 \({f(i)}={∑_{j⊆i}}{a_j}\) 。
例 \({f(11)}={a_0}+{a_1}+{a_2}+{a_3}+{a_8}+{a_9}+{a_{10}}+{a_{11}}\) 。
其中 \(0|11=11\) 、 \(1|11=11\) 、 \(2|11=11\) 、 \(3|11=11\) 、 \(8|11=11\) 、 \(9|11=11\) 、 \(10|11=11\) 、 \(11|11=11\) 。
请求出 \({\sum_{i=0}^{{2^p}-1}}{f(i)}={f(0)}+{f(1)}+{f(2)}+{\dots}+{f({{2^p}-1})}\) 的值。答案对 998244353 取模。
输入格式
输入的第一行包含一个正整数 \(p\) 。
第二行以空格隔开输入 \(2^p\) 个整数，分别表示 \({a_0},{a_1},{\dots},{a_{{2^p}-1}}\) 。
输出格式
输出一行一个整数，表示答案的值。
数据范围
对于 100% 的数据， \(1≤p≤18,0≤{a_i}≤{10^9}\) 。
各测试点的附加限制如下表所示：
测试点编号 p≤ 特殊性质 1∼8 5 9∼14 9 15∼16 13 保证所有 a[i] 相等 17∼20 18
格式说明
输出时每行末尾的多余空格，不影响答案正确性
输入、输出要求
要求使用「文件输入、输出」的方式解题，输入文件为 func.in，输出文件为 func.out
按：func 是 function 的缩写，意为函数。
样例输入1
2
0 1 2 3
样例输出1
9
样例解释1
\({f(0)}={a_0}={0}\)
\({f(1)}={a_0}+{a_1}={1}\)
\({f(2)}={a_0}+{a_2}={2}\)
\({f(3)}={a_0}+{a_1}+{a_2}+{a_3}={6}\)
因此，答案是 \(0+1+2+6=9\) 。
样例输入2
4
6 15 7 15 19 4 1 5 15 20 5 14 11 20 3 4
样例输出2
856
样例解释2
\({f(0)}={a_0}={6}\)
\({f(1)}={a_0}+{a_1}={21}\)
\({f(2)}={a_0}+{a_2}={13}\)
\({f(3)}={a_0}+{a_1}+{a_2}+{a_3}={43}\)
\({f(4)}={a_0}+{a_4}={25}\)
\({f(5)}={a_0}+{a_1}+{a_4}+{a_5}={44}\)
\({f(6)}={a_0}+{a_2}+{a_4}+{a_6}={33}\)
\({f(7)}={a_0}+{a_1}+{a_2}+{a_3}+{a_4}+{a_5}+{a_6}+{a_7}={72}\)
\({f(8)}={a_0}+{a_8}={21}\)
\({f(9)}={a_0}+{a_1}+{a_8}+{a_9}={56}\)
\({f(10)}={a_0}+{a_2}+{a_8}+{a_{10}}={33}\)
\({f(11)}={a_0}+{a_1}+{a_2}+{a_3}+{a_{8}}+{a_{9}}+{a_{10}}+{a_{11}}={97}\)
\({f(12)}={a_0}+{a_4}+{a_8}+{a_{12}}={51}\)
\({f(13)}={a_0}+{a_1}+{a_4}+{a_5}+{a_{8}}+{a_{9}}+{a_{12}}+{a_{13}}={110}\)
\({f(14)}={a_0}+{a_2}+{a_4}+{a_6}+{a_{8}}+{a_{10}}+{a_{12}}+{a_{14}}={67}\)
\({f(15)}={a_0}+{a_1}+{a_2}+{a_3}+{a_4}+{a_5}+{a_6}+{a_7}+{a_{8}}+{a_{9}}+{a_{10}}+{a_{11}}+{a_{12}}+{a_{13}}+{a_{14}}+{a_{15}}={164}\)
因此，答案是 \(6+21+13+43+25+44+33+72+21+56+33+97+51+110+67+164=856\) 。
【解析】
对于每个 \({a_i}\) 考虑贡献，会被计算 \(2^{n-{popcount(i)}}\) 次，其中 \(popcount(i)\) 表示 \(i\) 的二进制数中 \(1\) 的个数。
证明：一个完整二进制长度为 \(n\) ，那如果要让 \({a_i}\) 这个元素产生贡献，那么这个数在 \(i\) 所有为 \(1\) 的数位上必须都为 \(1\) ，剩余部分可为 \(0\) 或 \(1\) ，所以在 \(2^n\) 中，会有 \(2^{n-{popcount(i)}}\) 包含 \({a_i}\) 。
时间复杂度 \(O({n{\log{n}}})\) ，如果使用 __builtin_popcount 可以做到 \(O(n)\) 。
【参考代码】
按：popcount 是 population count 的缩写，也叫 sideways sum （数位叠加和），是计算一个整数的二进制表示有多少位是 1 。
按：ios::sync_with_stdio(false); 参考 https://xinxixue.com/i2s7yn
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, Mod = 998244353;
int main() {
freopen("func.in", "r", stdin);
freopen("func.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int p, n;
cin >> p;
n = (1 << p);
long long sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum = (sum + (1ll << (p - __builtin_popcount(i))) * x % Mod) % Mod;
}
cout << sum;
return 0;
}