题目出自2024-2025A10联盟数学 T19

这一题如果学过编程那么其实很容易有思路

这一题让求"递嬗和"和"递嬗积"。只节选"递嬗和"的部分，"递嬗积"部分我改天写，那个太难想了。原题中具体的集合换成未知的

题目

对集合\{x|\in Z\}及其每一个非空子集 A ，定义一个唯一确定的”递嬗和“如下，将A中的数按照递减的次序排列，然后第一个数减第二个数，再加上第三个数，再减去第四个数....减加交替所得的结果，例如 \{2,4,6,7,8\}的"递嬗和"是8-7+6-4+2=5。现在，有一个集合中A有n个元素，求集合A中所有非空子集的"递嬗和"的总和。

思考

暴力

看到这个题目，第一眼想到的就是暴力计算，也就是按照题目要求枚举出来所有子集,每个子集的结果加一块。

然而1s只能处理 n ≤ 20 的情况。如果是手算,n=5的时候非空子集就有31个了，很不好算

所以这一题是一定可以优化的

优化思路

首先明确：集合中第1 3 5 7...个元素对最终结果贡献是正，而第2 4 6 8...个元素对最终结果贡献是负

现在我们的数组是a[1...n] 并且他已经是有序的且是递减排序的，也就是a[1]>=a[2]>=a[3]>=....>=a[n]

所以a[i]为奇数时，贡献为

这个时候我们对某一个a[i]进行思考，思考它在所有子集中的净贡献val (value)

我们这里先设a[i]在某一个子集B中，出现的位置是第k个，则：

k为奇数时净贡献为a[i]

k为偶数时净贡献为-a[i]

那很显然，你有多少个k为奇数，你贡献就是多少个a[i]。反之你有多少个k为偶数，你贡献就是多少个-a[i]。

不难推出：

val(a[i]) = a[i] \times \left( \sum_{\substack{B \subseteq A \\ a[i] \in B \\ k为奇数}} 1 - \sum_{\substack{B \subseteq A \\ a[i] \in B \\ k为偶数}} 1 \right)

那么我们这时就需要想，我怎么知道我有多少个k为奇数，有多少个k为偶数？

思考发现，a[i]出现在第k个位置，需要满足3个条件：

1.这个集合B必须包含a[i]。这个不用多说

2.子集必须包含恰好 k-1个比 a[i] 大的元素。这句话什么意思，就是说，我要求我这个a[i]是在第k个位置，那前面得有k-1个比他大的才行。比如，a[i]前面有2个元素，那很显然我这个a[i]就是第3个位置

3.比 a[i]小的元素可以任意选择。这是因为，你a[i]的位置已经固定了，那么后面比他小的数，无论怎么选，甚至他后面不选了，你这个数a[i]在这个子集中贡献不变，因为他取决的就是你从前往后数的第k个位置，与后面无关

由此我们又推出：选择比 a[i]大的元素和选择比 a[i]小的元素是相互独立的事件。

根据排列组合的知识，不难发现，你在a[i]在第k个位置前，是从i-1个数里面，挑选出k-1个数。在k后，你有 n-i个元素，然后他们可以随便选，子集一共是 2^{n-i} 个。所以 a[i]出现在第 k个位置的子集数量为：

\begin{pmatrix}i-1 \\ k-1 \end{pmatrix}2^{n-i}

然后代入我们推导的上一个式子

val(a[i])=a[i]\times \sum_{k=1}^{i} \begin{bmatrix} (-1)^{k-1} \times \begin{pmatrix}i-1 \\ k-1 \end{pmatrix}\times 2^{n-i} \end{bmatrix}

令 j=k-1进一步化简，另外因为这个2的n-i次方是跟这个j没有关系的所以提取到外面

val(a[i])=a[i]\times 2^{n-i}\times\sum_{j=0}^{i-1} \begin{bmatrix} (-1)^{j} \times \begin{pmatrix}i-1 \\j \end{pmatrix} \end{bmatrix}

然后最难的地方来了，因为这个你不知道的话，你是推不出来下一步的：

这个东西就是二项式定理，也就是

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

观察发现，这里让a=1,b=-1,n=i-1 那么

(1+(-1))^i= \sum_{j=0}^{i-1} \binom{i-1}{j} ^{i-1-j} (-1)^j

于是啊我们发现，最后这个东西变成了 0^i，那么我们知道，在组合数学中特别规定，0的0次方等于1，所以i=1时，这个结果为1，i>1时，结果为0

也就是说，我们可以理解为，在我们原始的集合A中，除了最大的那个数也就是a[1]，i>1时，它的结果就是0

所以，我们最后的答案只跟a[1]有关

推出最终结果

总贡献=a[1]\times 2^{n-1}