自动搬运

查看原文

来自洛谷，原作者为

	泥土笨笨 《算法竞赛实战笔记》作者

搬运于2025-08-24 22:22:02，当前版本为作者最后更新于2020-05-28 16:05:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写一个复杂度$O(3^{18})$的题解吧，思路简单一些，虽然复杂度高，但是能过。部分参考了我校大神@dengyaotriangle 的题解，感谢。

首先，我们把每一个数字看成是一个集合。每个数字可以写成二进制，那么看这个二进制形式中，从右往左的每个位置上的数字。如果第i位上是1，表示这个集合中有$2^i$，否则表示这个集合中没有$2^i$。这里i从0开始。下文中，我们用小写字母表示数字，对应的大写字母表示集合。

举个例子，数字5对应成二进制是$(101)_2$，那么把5看成是集合$\{ 2^0,2^2 \}$。数字9对应二进制是$(1001)_2$，表示$\{ 2^0,2^3 \}$。

现在要求我们找到一个子序列，子序列中任意两个数字a和b，都满足a&b==0，其实我们把a和b看成是两个集合A和B以后，这个条件等价于，A和B的交集是空集。

假设原序列中有一个合法的子序列S，x代表其中包含的数字。现在题目中要求的是$\sum_{x \in S}x$。有意思的是，因为其中任何两个数字的与都是0，所以它们加在一起不可能产生进位。那么要求的和可以看成是集合的并，即我们要求转化为$\cup_{X \in S}X$。设一个合法序列S中所有数字的和为sum，那么根据题中的数据范围，我们知道$sum<=4*10^{5}$，大概是$2^{18}$左右。

设dp[i]表示合法序列中所有元素的和为i的方案数，设phi[i]数组表示i的欧拉函数的结果。其中phi数组可以线性求出，如果不会，可以参考模板题SP4141 ETF - Euler Totient Function

那么最终答案就是

所以问题的关键变成，如何求dp数组？0比较特殊，暂时认为数列里面没有0，后面咱们再单独处理。

假设目前正在求dp[sum]，表示现在合法序列的数字和是sum的方案数。首先观察发现，这些合法数字，一定都是小于等于sum的。而且题目中问我们子序列的方案数，子序列本身是和顺序无关的。所以提示我们，输入完成以后，可以把数组按照从小到大的顺序排序。

再考虑，dp[sum]可能从哪些点转移过来？能转移过来的点，一定是sum对应的集合SUM的子集。那么我们枚举SUM的子集X，对应的数字是x。并设X在SUM中的补集是Y，并且设c[x]表示x这个数字在原来序列中出现的次数，那么有

解释一下，X是SUM的子集，Y是补集，那么dp[y]表示的是这个补集的方案数。对于这里的每个方案，加上一个x，都可以得到一个和为sum的方案。而x有多少个，从中任选一个均可，所以乘上一个x的个数c[x]。相信读者现在能理解这个递推式了。因为这里需要按照从小到大的顺序递推，并且需要求每个数字出现的次数，所以提示我们，输入的时候，干脆把这些数字存在桶里面。这样从小到大扫一遍桶，就可以做递推了。

这里还有个问题是如何枚举SUM集合的子集。实现的代码模板是：

for (int s = i;/*结束的条件先空着一会儿说*/; s = (s - 1) & i) {
    //s是i的子集
    int bu = i ^s;//bu是s在i中的补集
}

这段代码里面是在枚举i的子集s，还顺便求出了补集bu。什么原理呢？

不妨先举个例子，假设i最开始是5，二进制表示是101，第一次s等于i，找到了101这个子集，其实就是它自己。

然后s变成s-1，即为100，然后用它与上i本身，即为100&101，是100，这是第二个子集。

然后s变成s-1，即为11，然后用它与上i本身，即为11&101，是1，这是第三个子集。

我们看这个过程，确实找到了i的每一个子集，如何理解呢？首先s等于i不用解释了，然后我们想，下一个子集肯定要比现在的s小，所以先减掉1肯定是变小了。其实是把最右边一个1变成了0，然后把它后面的0都变成了1.然后子集里面的数字，必须是原来i里面是1的位置，才能是1，所以正好与上i，把刚刚变成1的那些0里面的多余的i去掉，这样就成功得到了下一个更小的子集。

补集bu比较好理解，用i异或一下s，表示把s里面每个1对应的位置，从i中去掉。这样正好是补集。

所以回到求dp[sum]的位置，现在依次枚举SUM的子集，然后转移是不是就可以了呢？其实还有点小问题，这样算其实算重复了。比如3可以拆成1和2，在s等于1的时候算了一次，这时候补集是2。在s等于2的时候算了一次，这时候补集是1。但是其实是一种情况。如何避免算重复呢？我们只要保证s比bu大就行了。这样每次都是s和前面的dp[bu]一起算，就不会重复。所以枚举子集的时候，遇到s<bu就break。

最后考虑一下0，其实原来序列里面如果有cnt个0，那么对于原来每一种方案，都可以从cnt个0里面任取若干个组成新方案，所以方案数要乘一个$2^{cnt}$，这个最后算完了以后统一处理即可。

最后分析一下这么做的时间复杂度。先给出一个结论，n个元素组成的集合的子集的子集的方案数是$O(3^n)$，这道题中因为数据范围限制，每个数最多也就是18位，i依次取18个数的某一个子集，然后又枚举i的子集s，所以恰好总复杂度就是18个数的子集的子集的个数，所以DP过程复杂度大概是$O(3^{18})$

再加上最后枚举一遍DP数组的复杂度，大概是$O(n+3^{18})$

那么如何证明这个结论呢？

这个证明不是很难 ————@dengyaotriangle

对于原集合S，它有子集S'，和它的子集S''，那么对于每一个(S',S'')，考虑S中每一个元素u，那么只有三种情况，（u不属于S',u不属于S''）；（u属于S'，u不属于S''）；（u属于S'，u属于S''），这样，每个元素u都有3种可能性，而元素间互相独立，所以一共是$3^n$种可能的(S',S'')，也就是集合的子集的子集的个数为$3^n$

另外提供一种使用二项式定理的证明方式。首先，二项式定理是：

而n个元素中，有k个元素的集合的数量是${n \choose k}$，而k个元素的集合的子集的个数是$2^k$，所以子集的子集的总个数是$\sum {n \choose k}2^k$

它等于

最后是喜闻乐见的代码时间了，注释比较少，有问题可以在评论区里面留言

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;
const ll MAXN = 400005;
const ll MOD = 1000000007;
ll n, a[MAXN], dp[MAXN], phi[MAXN], m, ma;//ma是a中的最大值，m是最大值的位数
ll prime[MAXN], pc;

void eulerTable(int x) {
    phi[1] = 1;
    for (int i = 2; i <= x; ++i) {
        if (phi[i] == 0) {
            prime[pc++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < pc && prime[j] * i <= x; ++j) {
            if (i % prime[j] == 0) {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            } else {
                phi[prime[j] * i] = (prime[j] - 1) * phi[i];
            }
        }
    }
}

int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; ++i) {
        ll t;
        scanf("%lld", &t);
        a[t]++;
        ma = max(ma, t);
    }
    while ((1 << m) <= ma) { m++; }
    eulerTable(1 << m);
    dp[0] = 1;
    for (int i = 1; i <= (1 << m); ++i) {
        for (int s = i;; s = (s - 1) & i) {
            //s是i的子集
            int bu = i ^s;//bu是s在i中的补集
            if (s < bu) break;
            dp[i] = (dp[i] + dp[bu] * a[s]) % MOD;
        }
    }
    ll ans = 1;//加上空集
    for (int i = 1; i <= (1 << m); ++i) {
        ans = (ans + dp[i] * phi[i + 1]) % MOD;
    }
    for (int i = 0; i < a[0]; ++i) {
        ans = ans * 2 % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}