P6570 [NOI Online #3 提高组]优秀子序列题解

泥土笨笨

2020-05-28 16:05:01

Solution

写一个复杂度$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; } ```