python- 算法题-8_找出所有子集的异或总和再求和_扩展

一、排列公式(有顺序)

排列公式： $A_n^k$ ，其中 $n$ 表示要进行排列的对象总数， $k$ 表示要选择的对象个数。

$A_n^k = n(n-1)(n-2) ... (n-n+1(=1))$ , 其中 n (n-1) (n-2) ... 的个数为 $k$ 个，从大到小，多余的删除。
或者写成下述方式
$A_n^k = \frac{n!}{(n-k)!}$
其中，(n!) 表示 n 的阶乘，即从 1 到 n 的连续整数的乘积，(n-k)! 表示 (n-k) 的阶乘。

$A_6^2 = 6\times5 = 30$
$A_6^2 = \frac{6!}{(6-2)!} = \frac{6\times5\times4\times3\times2\times1}{4\times3\times2\times1} = 30$

例如：我们要从1、2、3这三个数字中选择2个进行排列(注意不是组合)。

根据排列公式 $A_3^2 = 3 \times 2 = 6$ ，我们得到的结果是6，这表示从1、2、3这三个数字中选择2个进行排列，共有6种可能的情况。这些情况包括：

1-2
1-3
2-1
2-3
3-1
3-2

每对数字的顺序都是不同的，因此总共有6种可能。

二、组合公式(没有顺序)

排列公式： $C_n^k$ ，其中 $n$ 表示要进行排列的对象总数， $k$ 表示要选择的对象个数。

$C_n^k = \frac{n(n-1)(n-2)...(n-n+1(=1))}{k!}$ ，其中 n (n-1) (n-2) ... 的个数为 $k$ 个，从大到小，多余的删除。
或者写成下述方式
$C_n^k = \frac{n!}{k!(n-k)!}$
其中，(n!) 表示 n 的阶乘，即从 1 到 n 的连续整数的乘积；(k!) 表示 k 的阶乘；(n-k)! 表示 (n-k) 的阶乘。

特殊性质1： $a + b = n$ , $C_n^a=C_n^b$

例如1： a=1,b=2,n=3
$C_3^1=\frac{3}{1}=3$
$C_3^2=\frac{3 \times 2}{1 \times 2}=3$

例如2：a=3,b=4,n=7
$C_7^3=\frac{7 \times 6 \times 5}{1 \times 2 \times 3}=35$
$C_7^4=\frac{7 \times 6 \times 5 \times 4}{1 \times 2 \times 3 \times 4}=35$

特殊性质2： $C_n^n=C_n^0=1$

$C_n^n$ 表示n个对象选取n个，这种集合只有一种，所以等于 1 。
$C_n^0$ 表示n个对象选取0个，空集只有一种，所以等于 1 ；也有另一种解释 $n + 0 = n$ ,所以 $C_n^n=C_n^0$ ，所以 $C_n^0=C_n^n=1$

对于给定的 3 个对象：1、2、3，我们可以计算出不考虑选择几个对象的情况下的总组合数。

通过组合公式，我们可以得到：

$C_3^0=1 \text{ 选择对象为0个的可能组合有多少种}$
$C_3^1=3 \text{ 选择对象为1个的可能组合有多少种}$
$C_3^2=3 \text{ 选择对象为2个的可能组合有多少种}$
$C_3^3=1 \text{ 选择对象为3个的可能组合有多少种}$

将这些组合数相加，得到总共的组合数为：

$C_3^0 + C_3^1 + C_3^2 + C_3^3 = 1 + 3 + 3 + 1 = 8$

我们可以观察到，这个结果等于 $2^3$ 。这是因为，在每个位置上，我们有两个选择：选择该位置的对象或不选择该位置的对象。在 3 个位置上，共有 $2 \times 2 \times 2 = 2^3$ 种可能性。

三、二项式定理

$(a+b)^2=a^2+2 \times a \times b+b^2$
$(a+b)^3=a^3+3 \times a^2 \times b+3 \times a \times b^2+b^3$

$(a+b)^2=C_2^0 \times a^2 + C_2^1 \times a \times b + C_2^2 \times b^2$
$(a+b)^3=C_3^0 \times a^3 + C_3^1 \times a^2 \times b + C_3^2 \times a \times b^2 + C_3^3 \times b^3$
$\cdots$
$(a+b)^n=C_n^0 \times a^n \times b^0 + C_n^1 \times a^{(n-1)} \times b^1 \cdots C_n^{(n-1)} \times a^{(n-(n-1))} \times b^{(n-1)} + C_n^n \times a^{(n-n)} \times b^n$
$(a+b)^n=C_n^0 \times a^n + C_n^1 \times a^{(n-1)} \times b^1 \cdots C_n^{(n-1)} \times a^1 \times b^{(n-1)} + C_n^n \times b^n$
$(a+b)^n=\sum_{r=0}^n C_n^r a^{n-r}b^r \text{ 其中 r 的范围为 0 到 n}$
或
$(a+b)^n=\sum_{r=0}^n C_n^r a^rb^{n-r} \text{ 其中 r 的范围为 0 到 n}$

通项公式： $C_n^r a^{n-r}b^r$ $=$ $C_n^r a^rb^{n-r}$ , 其中 r 的取值为 0 到 n 。

项数等于 n + 1 。
$C_n^r$ 为项( $a^{n-r}b^r$ )的系数。

扩展：系数

在数学中，系数是指一个数与某个变量或项之间的乘法关系中的常数因子。它通常用于代数表达式中，表示变量或项与其前面的常数的乘积。

在代数表达式中，常见的形式是ax，其中a是系数，x是变量。系数可以是整数、有理数或实数。它用于表示变量的数量、大小或比例关系。

举例来说，在代数表达式2x^2 + 3x + 1中，2是 x^2 的系数，3是x的系数，而1可以看作是常数1与x^0（也就是常数项）的系数。

系数在代数中起着重要的作用，它们决定了变量或项在表达式中的贡献和权重。通过改变系数的值，可以调整变量或项对整体表达式的影响程度。系数也可以用于解方程、求导、展开多项式等数学运算中。

扩展1：求和 ( $\sum$ )

符号 $\sum$ 是用来表示求和的。在数学中，它表示我们将一系列的项相加求和。这些项可以按照上下文的要求进行加法或减法运算。

例如，如果我们有一系列的数字 $a_1，a_2，a_3，\dots，a_n$ ，那么这些数字的和可以用求和符号表示为 $\sum_{i=1}^n a_i$ 。这意味着我们要对所有的项 $a_i$ （其中 $i$ 从1到 $n$ ）进行求和。

求和符号中的索引 $i$ 表示要求和的项在序列中的位置。在上面的例子中， $i$ 的取值范围是从1到 $n$ ，因此我们要对序列中的所有项进行求和。

求和的结果是一个单一的值，它是所有项相加或相减的和。这个值是按照加法和减法的规则得到的。

求和符号也可以在符号下面或上面指定额外的条件或约束。例如， $\sum_{i=1}^n a_i$ 表示我们对从1到 $n$ 的项 $a_i$ 进行求和。如果有额外的约束条件，它们被称为求和的限制。

总的来说，求和符号是数学中用来表示一系列项的总和的一种便捷的记号。它被广泛应用于各个数学分支，包括代数、微积分和数论。

扩展2：

$C_n^k$ 的另一种常见写法是 $\binom{n}{k}$ 。这种写法使用了二项式系数的表示方法。

在组合数学中， $C_n^k$ 表示从 $n$ 个元素中取 $k$ 个元素的组合数，也就是从 $n$ 个元素中选取 $k$ 个元素的可能性的数量。

使用 $\binom{n}{k}$ 的写法，可以更清晰地表示出这种组合数的意义。在这个写法中， $\binom{n}{k}$ 表示从 $n$ 中选择 $k$ 个元素的组合数。

这里的 $\binom{n}{k}$ 读作"n choose k"，它是用来表示组合数的一种常见记号。 $\binom{n}{k}$ 可以通过以下公式进行计算：

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

其中 $n!$ 表示 $n$ 的阶乘，即 $n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$ 。

这种写法更加直观地表示了组合数的含义，同时也更加符合数学符号的常规用法。所以，在组合数学中， $\binom{n}{k}$ 是较常用的表示方法之一。

扩展3：

(-1)^N的结果取决于奇偶性是由数学规律决定的。
当指数为偶数时，(-1)^N的结果为1。
当指数为奇数时，(-1)^N的结果为-1。

简而言之，(-1)^N的值取决于N的奇偶性。
如果N是偶数，(-1)^N等于1；
如果N是奇数，(-1)^N等于-1。

解释：
当一个数的指数是偶数时，例如2、4、6等，那么(-1)的任何偶次幂得到的结果都是1。这是因为在乘法中，负数乘以负数得到正数，即(-1) * (-1) = 1。当偶次幂相乘时，每个(-1)都会被消除，最终结果为1。

而当一个数的指数是奇数时，例如1、3、5等，那么(-1)的奇次幂得到的结果都是-1。这是因为在乘法中，负数乘以负数得到正数，即(-1) * (-1) = 1。当奇次幂相乘时，仍然存在一个(-1)无法被消除，最终结果为-1。

因此，根据乘法的规则以及(-1)的性质，(-1)^N的结果取决于N的奇偶性。

负数的幂运算可以通过将其转化为倒数和正数的幂运算来处理。具体来说，对于一个实数 a 和一个整数 n：

当 n 是偶数时，(-a)^n = a^n。
当 n 是奇数时，(-a)^n = -a^n。

这是因为负数的偶次幂得到的结果是正数，而负数的奇次幂得到的结果是负数。

需要注意的是，如果 n 是分数或者实数，负数的幂运算并没有明确的定义，因为它涉及到复数和复数幂的概念。在复数领域中，涉及到幅角、辐角、共轭复数等概念来描述负数的幂运算。

综上所述，负数的幂运算涉及到指数的奇偶性，并且结果可能是正数或负数，具体要根据指数的奇偶性来确定。
任何数的零次方都等于 1 。

扩展4： $(1-1)^n$ 二项式展开

当n=5, 奇数。
$(1-1)^5 = C_5^0 1^0- 1^5 + C_5^1 1^1 -1^4 + C_5^2 1^2 -1^3 + C_5^3 1^3 -1^2 +C_5^4 1^4 -1^1 + C_5^5 1^5 -1^0 \\ (1-1)^5 = C_5^0 -1 + C_5^1 1 + C_5^2 -1 + C_5^3 1 +C_5^4 -1 + C_5^5 1 \\ (0^5)0 = C_5^0 -1 + C_5^1 1 + C_5^2 -1 + C_5^3 1 +C_5^4 -1 + C_5^5 1 \\ C_5^1 1 + C_5^3 1 + C_5^5 1 = 0 + C_5^0 1 + C_5^2 1 + C_5^4 1\\ C_5^1 1 + C_5^3 1 + C_5^5 1 = C_5^0 1 + C_5^2 1 + C_5^4 1\\ C_5^1 + C_5^3 + C_5^5 = C_5^0 + C_5^2 + C_5^4 \\ 5 + 10 + 1 = 1 + 10 + 5 \\ 16 = 16 = 2^4 = 2^{5-1} = 2^{n-1}$
当n=6, 偶数。
$(1-1)^6=C_6^0 1^0 -1^{6-0} + C_6^1 1^1 -1^{6-1} + C_6^2 1^2 -1^{6-2} + C_6^3 1^3 -1^{6-3} + C_6^4 1^4 -1^{6-4} + C_6^5 1^5 -1^{6-5} + C_6^6 1^6 -1^{6-6} \\ (1-1)^6=C_6^0 1^0 -1^6 + C_6^1 1^1 -1^5 + C_6^2 1^2 -1^4 + C_6^3 1^3 -1^3 + C_6^4 1^4 -1^2 + C_6^5 1^5 -1^1 + C_6^6 1^6 -1^0 \\ (1-1)^6=C_6^0 1 + C_6^1 -1 + C_6^2 1 + C_6^3 -1 + C_6^4 1 + C_6^5 -1 + C_6^6 1 \\ (0^6)0=C_6^0 1 + C_6^1 -1 + C_6^2 1 + C_6^3 -1 + C_6^4 1 + C_6^5 -1 + C_6^6 1 \\ C_6^0 1 + C_6^2 1 + C_6^4 1 + C_6^6 1 = 0 + C_6^1 1 + C_6^3 1 + C_6^5 1 \\ C_6^0 1 + C_6^2 1 + C_6^4 1 + C_6^6 1 = C_6^1 1 + C_6^3 1 + C_6^5 1 \\ C_6^0 + C_6^2 + C_6^4 + C_6^6 = C_6^1 + C_6^3 + C_6^5 \\ 1 + 15 + 15 + 1 = 6 + 20 + 6 \\ 32 = 32 = 2 ^ 5 = 2^{6-1} = 2^{n-1}$

所以二项式系数： $\text{奇数项系数之和} = \text{偶数项系数之和} = 2^{n-1}$

如有错误欢迎指正，谢谢！

参考：
https://www.bilibili.com/video/BV1Yq4y1E7JF/?spm_id_from=333.337.search-card.all.click&vd_source=fd551c73306d10ac7c5d19c2369e1ce3
https://www.bilibili.com/video/BV1pb4y1X7AA/?spm_id_from=333.337.search-card.all.click&vd_source=fd551c73306d10ac7c5d19c2369e1ce3

def subsetXORSum(nums: list[int]) -> int:
    res = 0
    n = len(nums)

    # nums集合中 元素的二进制某一位上有1的位置才会影响最终结果
    # 汇总nums集合中所有元素二进制上所有的1
    for num in nums:
        res |= num

    # n个元素整个集合的大小（含空集）是2^n
    # 根据数学推论，二进制某一位上有1的元素，在最终的集合中，一半0一半1
    # 所以把前面的汇总结果乘以2^n / 2，即2^(n-1)
    # res << (n-1) 等于 res * 2^(n-1)
    return res << (n - 1)

#nums = [1, 3]
#nums = [5, 1, 6]
nums = [3, 4, 5, 6, 7, 8]
print(subsetXORSum(nums))

以下是对上一段脚本的解释：

例1
答案：
110  <-  6


nums集合内的元素：
001  <-  1
011  <-  3

所有组合：
000  <-  空
001  <-  1
011  <-  3
010  <-  2  <-  1^3
         6

# 在上上述组合中出现的次数。
001 * 2(2**(2-1))  =  2
010 * 2(2**(2-1))  =  4


11  <-  3  <-  (1 | 3)
110 <-  6  <-  3<<(2-1)


------------------------------------------------

例2
答案: 
1100  <- 12


nums集合内的元素：
001  <-  1
010  <-  2
011  <-  3

所有组合(2**3=8)：
000  <-  空
001  <-  1
010  <-  2
011  <-  3
011  <-  3  <-  1^2
010  <-  2  <-  1^3
000  <-  0  <-  1^2^3
001  <-  1  <-  2^3
         12


010 * 4(2**(3-1))
001 * 4(2**(3-1))

11  <-  3  <- (1 | 2 | 3)
1100  <-  12  <- 3<<(3-1)


-----------------------------------------

例3
答案：28
11100


nums集合内的元素：
00001  <-  1
00100  <-  4
00110  <-  6

所有组合(2**3=8)：
00000  <-  空
00001  <-  1
00100  <-  4
00110  <-  6
00101  <-  5  <-  1^4
00111  <-  7  <-  1^6
00011  <-  3  <-  1^4^6
00010  <-  2  <-  4^6
           28


00001 * 4(2**(3-1))
00010 * 4(2**(3-1))
00100 * 4(2**(3-1))

111  <-  7 <- (1 | 4 | 6)   
11100  <-  28  <-  7<<(3-1)


通过上述3个例子,可以得出下面的结论：

nums集合中有 n 元素，它的所有子集的异或总和为  它的所有元素的 或 结果 位运算向左位移(n-1)。或者说结果乘以 2的(n-1) 次方。
nums = [a1, a2, a3, ...]
nums 所有子集的异或总和 = (a1 | a2 | a3 ...) << (n-1) = (a1 | a2 | a3 ...) * 2**(n-1)

例如：
nums = [1, 4, 6]
n = len(nums)
res = 0
for L in nums:
    res = res | L

res = res << (n-1)
print(nums, '所有子集的异或总和为：', res)

一个数组的所有组合有 2^n 种(包括一个空集)，n 为数组中元素的个数。
对于一个正数，它的每个二进制位都是 0 或 1。

如果数组中所有元素该位都是0，最终每种组合所有数该位必为0，异或和贡献也为0；
如果数组中所有元素该位有一个或多个1时，则最终贡献必有一半是1。(另一半是0)。

所以数组中元素的或操作结果，就是数组中所有元素的二进制为1的结果，
然后乘以2^(n -1)即可得出数组的所有子集的异或结果的总和。

为什么乘以 2^(n-1) ，因为一个元素或多个元素的二进制某位为1，它在所有组合中异或结果的二进制中该位出现1的次数为所有组合( 2^n ) 的一半。
即 2^n / 2 = 2^(n-1)

一个整数 L， L * 2^(n-1) = L << (n-1)
尝试解释这个等式：
在十进制中 L * 10^m = L << m （L的十进制向左移动m位然后补m个0。）
 L=3,m=3  3 * 10^3 = 3000
          3 * 1000 = 3000
              3000 = 3000
同理在二进制中  L * 2^m = L << m （L的二进制向左移动m位然后补m个零。）
 L=3,m=3       3 * 2^3 = 11 << 3
                 3 * 8 = 11000
                    24 = 24

例： 组合中元素分别为 1, 4, 6 ，n = 3。
001  <-  1
100  <-  4
110  <-  6
111
即 001 * 2^(3-1) + 010 * 2^(3-1) + 100 * 2^(3-1)    (这里的 001, 010, 100 是二进制)
= 1 * 4 + 2 * 4 + 4 * 4
= 28
或 001 << (3-1) + 010 << (3-1) + 100 << (3-1)    (这里的 001, 010, 100 是二进制)
= 00100 + 0100 + 10000
= 4 + 8 + 16
= 28

对于力扣官方关于这种解法的解释，目前我还无法彻底理解并清晰地解释出来。在我思考透彻后，我会进行更新。如果有任何能够帮助解释的人，欢迎指正和提供帮助。

参考：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/solution/zljhero-zhao-chu-suo-you-zi-ji-de-yi-huo-dax1/

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,686评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,668评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,160评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,736评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,847评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,043评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,129评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,872评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,318评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,645评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,777评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,470评论 4赞 333
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,126评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,861评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,095评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,589评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,687评论 2赞 351