计蒜客CSP-J2模拟赛：函数

2023年10月6日 | 分类: 【编程】

【题面】

题目描述

对于两个非负整数 $a, b$ ，如果 $a ∣ b = b$ ，则称 $a$ 是 $b$ 的子集，记作 $a \subseteq b$ 。其中 $∣$ 表示按“位或”运算。

给定一个长度为 $2^{p}$ 的序列 $a_{0}, a_{1}, \dots, a_{2^{p} - 1}$ 。
我们定义函数 $f (i) = \sum_{j \subseteq 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 \leq p \leq 18, 0 \leq a_{i} \leq 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 - p o p c o u n t (i)}$ 次，其中 $p o p c o u n t (i)$ 表示 $i$ 的二进制数中 $1$ 的个数。

证明：一个完整二进制长度为 $n$ ，那如果要让 $a_{i}$ 这个元素产生贡献，那么这个数在 $i$ 所有为 $1$ 的数位上必须都为 $1$ ，剩余部分可为 $0$ 或 $1$ ，所以在 $2^{n}$ 中，会有 $2^{n - p o p c o u n t (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;
}