可能发现了一个结论，求问是否正确

rt，本帖在站外也发过，但是无人回复。最近刚升橙名，突然想起来，发一下看看有无大佬帮助。

一道站外题，描述如下：

给定一个正整数 $n$ ，以及一个长度为 $n$ 的整数序列 $A = \{A_1,A_2,\dots,A_n\}$ ，对任意子集 $S \subseteq \{1,2,\dots,n\}$ 定义该子集的权值为 $w(S)=\sum_{i\in S} A_i$ 定义所有子集权值的总和为 $F=\sum_{S\subseteq\{1,2,\dots,n\}} w(S)$

请你计算 $F$ 。

这题模拟拿了

25

pts，看题解。

这题题解里有这样一条结论：

\sum_{S\subseteq[n]} \sum_{i\in S} A_i = \sum_{i=1}^{n} A_i \cdot 2^{\,n-1}

并给出了一道变式题，如下：

给定长度为 $N$ 的整数序列 $A_1,A_2,\dots,A_N$ 。

定义：

$S \subseteq \{1,2,\dots,N\}$ ：一个非空子集（集合）

$T(S)=\sum_{i\in S}A_i$ ：子集 $S$ 的子集和

$f(S)=T(S)\bmod 10^5 + 1$ 。

求 $f(S)$ 的所有可能值之和 $\pmod{998244353}$ 。

想了 1 day，突然想到了一点，加上 tbh 同学的帮助，拼出了这个式子：

\boxed{ \sum f(S) = 2^{N-1}\cdot (\sum_{i=1}^N A_i) - (10^5 + 1) \cdot(\text{子集和}\ge P\text{ 的子集个数}) }

验证了一下没有问题。

但是不知道是不是一定对的，所以求问一下。

可能发现了一个结论，求问是否正确

讨论操作

回复

相关推荐

可能发现了一个结论，求问是否正确