P6570 [NOI Online #3 提高组]优秀子序列题解
泥土笨笨
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](https://www.luogu.com.cn/problem/SP4141)
那么最终答案就是
$$\sum dp[x]phi[x+1]$$
所以问题的关键变成,如何求dp数组?0比较特殊,暂时认为数列里面没有0,后面咱们再单独处理。
假设目前正在求dp[sum],表示现在合法序列的数字和是sum的方案数。首先观察发现,这些合法数字,一定都是小于等于sum的。而且题目中问我们子序列的方案数,子序列本身是和顺序无关的。所以提示我们,**输入完成以后,可以把数组按照从小到大的顺序排序。**
再考虑,dp[sum]可能从哪些点转移过来?能转移过来的点,一定是sum对应的集合SUM的子集。那么我们枚举SUM的子集X,对应的数字是x。并设X在SUM中的补集是Y,并且设c[x]表示x这个数字在原来序列中出现的次数,那么有
$$dp[sum]=\sum_{X \in SUM} dp[y]c[x]$$
解释一下,X是SUM的子集,Y是补集,那么dp[y]表示的是这个补集的方案数。对于这里的每个方案,加上一个x,都可以得到一个和为sum的方案。而x有多少个,从中任选一个均可,所以乘上一个x的个数c[x]。相信读者现在能理解这个递推式了。因为这里需要按照从小到大的顺序递推,并且需要求每个数字出现的次数,所以提示我们,输入的时候,干脆把这些数字存在桶里面。这样从小到大扫一遍桶,就可以做递推了。
这里还有个问题是如何枚举SUM集合的子集。实现的代码模板是:
```cpp
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$
另外提供一种使用二项式定理的证明方式。首先,二项式定理是:
$$(x+y)^n=\sum {n \choose k}x^ky^{n-k}$$
而n个元素中,有k个元素的集合的数量是${n \choose k}$,而k个元素的集合的子集的个数是$2^k$,所以子集的子集的总个数是$\sum {n \choose k}2^k$
它等于
$$ \sum {n \choose k}2^k1^{n-k} = (2+1)^n = 3^n$$
最后是喜闻乐见的代码时间了,注释比较少,有问题可以在评论区里面留言
```cpp
#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;
}
```