子异和 题解

# T4 子异和 题解 一棵树的部分显然可以用树链剖分变成跟一条链（或者说序列）一样的情况。所以我们这里只讨论序列的问题。 考虑暴力。显然，这道题没有$O(2^n)$的暴力分，所以我们考虑一种$O(n)$的求一个序列的子异和的方法。做这种题一般要用一种递推的思路，即已知前$k-1$个的答案，现在加入第$k$个，怎样用$O(1)$更新答案。 我们现在已知集合前$k-1$个数组成的集合的子异和，现在加入第$k$个数。则现在这个集合的子集可以分成两种情况，第一种为不包含第$k$个数的，另一种为包含前$k-1$个数且包含$k$，第三种情况为只包含$k$。不包含的我们不用考虑，因为已知，现在要处理的是包含第$k$个数的集合。如果将这些集合都去掉第$k$个数，那就变成了第一种情况（第三种情况变成空集），所以要考虑类似结合律的东西，即假设前$k-1$个数的答案为$s$，新加入的数为$new$，则$k$个数的答案就为$s+s\times new+new$，其中$+$和$\times$为某种运算。这个式子里的三项恰好分别对应着三种情况。现在，我们要定义$s$和$new$的类型以及$+$与$\times$。我们可以考虑单独维护每一个二进制位，即开一个$31$位数组来维护，令这个类型为$t$。我们定义$t$的第$i$位表示在目前的所有情况中，异或和的值第$i$位为$1$的数的个数。例如，已知所有情况为$1,3,6$，则$t$的第$1$位为$2$，因为有两个奇数。那么，$+$就可以定义为两个$t$类每一位都加起来得到的新$t$。$\times$的运算其实是第$k$个数异或前面的所有子集异或和的过程。如果$k$的第$i$位为$0$，则这一位不变，否则变为$0$的个数，即所有情况的数量减去$1$的个数。既然定义成功，我们就可以用$O(31n)$的复杂度维护序列啦！ ……相信大家没有怎么听得懂吧。这一部分确实有点难理解，请大家多想一想。我们来举个栗子。我们用$[]$表示一个$t$类。题面里的栗子：$\{1,2,3\}$。考虑前$1$个：$s$肯定是$[0,0,1]$（最右边的为第一位）。考虑前$2$个：$new$是$2$，即$[0,1,0]$。$s\times new$是$[0,1,1]$（只有第$2$位改变。原来的$s$第二位为$0$，总情况数为$1$（只有一个数当然只有一种啦），所以变为$1-0=1$）。再加上$s,new$，得到$[0,2,2]$。检验一下：$2*2+2*1=6$，确实为前两个数的子异和。考虑前$3$个数：$new$是$3$（$[0,1,1]$）。$s\times new$是$[0,2,2]$（$1,2$位改变，原来的$s$一二位为$1$，总情况数为$3$（前面有$2$个数，选取非空子集的方法数为$2^2-1=3$），所以新的$1,2$位为$3-1=2$）。加上$s,new$，得到$[0,4,4]$。检验一下：$2*4+1*4=12$，正确！ 以上就是暴力的算法，如果还不理解，自己再举几组栗子。 从上面$\{1,2,3\}$的栗子我们其实已经已经可以发现，$t$类中的所有数不是$0$就是另一个数，只有两种情况。多举几组栗子之后发现的确如此，且不是$0$的位上的数都是$2$的**集合大小减一**次方。 直接告诉大家结论吧：是$0$的位需要满足集合中所有数的那一位上的数都是$0$。其它不是$0$的位上的数都是$2$的**集合大小减一**次方。我们用数学归纳法对其进行证明： 1. 当只有一个数时，最终的$s$即此数的二进制表示，显然成立。 2. 若对于$k-1$个数结论成立，则加入第$k$个数时，对于每一位有四种情况：第一，原$s$和$new$的此位均为$0$，易得新的$s$此位仍为$0$；第二，原$s$此位为$2^{k-2}$，$new$此位为$0$，则新的$s$此位为$2^{k-2}+0+2^{k-2}=2^{k-1}$；第三，原$s$此位为$0$，$new$此位为$1$，则新的$s$此位为$((2^{k-1}-1)-0)+0+1=2^{k-1}$；第四，原$s$此位为$2^{k-2}$，$new$此位为$1$,则新的$s$此位为$((2^{k-1}-1)-2^{k-2})+2^{k-2}+1=2^{k-1}$。以上四种情况均符合前$k$个数的结论。所以对于$k$个数结论成立。 3. 综上，结论成立。 这个结论其实等价于：$\{a_1,a_2,…,a_n\}$的子异和为$(a_1 \|a_2\|…\|a_n)\times 2^{n-1}$。 然后我们就可以用线段树去维护这个东西了。 讲一讲区间修改。$lazytag$多重叠加的话异或在一起就好了。最关键的问题是怎么样$O(1)$得到一个区间内的数全部异或$k$（一个数）之后的**或**值（$pushdown$操作）。我们还是一位一位的考虑。如果$k$的此位为$0$，则与的结果肯定不变。如果在一段区间内，所有数的某一位上既有$1$又有$0$，那显然在异或之后此位的或运算的结果不变。只有在此位全为$1$或全为$0$的情况下，此位或运算的结果才会改变。怎么得到全为$1$或$0$的位呢？保存**与**和**或**的结果就可以了。设$man$为$2^{o}-1$，$o$是一个非常大的数，此区间的与值为$a$，或值为$b$，则或值会从$1$变为$0$的位有$k\&a$，从$0$变为$1$的位有$k\&(man⊕b)$。因此，$b$的值要$⊕a⊕b$。同理，$a$的值也要$⊕a⊕b$。剩下的就是线段树的事了。 标程： ``` #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<string> #include<iostream> using namespace std; int n,m,p; const long long mod=1000000007; inline void dy(int&a) { char c=0;a=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){a=(a<<1)+(a<<3)+c-'0';c=getchar();} } long long _2[300000]; struct Edge { int t,nexty; }edge[500000]; int head[500000],cnt=0; inline void add(int a,int b) { cnt++; edge[cnt].t=b; edge[cnt].nexty=head[a]; head[a]=cnt; } long long csz[500000],rea[500000]; int sz[500000],fa[500000],son[500000],dep[500000]; int bh[500000],lianfa[500000],js=0; long long man=2147483647; void dfs2(int node,int lf) { bh[node]=++js;lianfa[node]=lf;rea[js]=csz[node]; if(son[node])dfs2(son[node],lf); for(int i=head[node];i;i=edge[i].nexty) { if(edge[i].t==son[node]||edge[i].t==fa[node])continue; dfs2(edge[i].t,edge[i].t); } } void dfs1(int node) { sz[node]=1; for(int i=head[node];i;i=edge[i].nexty) { if(edge[i].t==fa[node])continue; fa[edge[i].t]=node; dep[edge[i].t]=dep[node]+1; dfs1(edge[i].t); if(sz[edge[i].t]>sz[son[node]])son[node]=edge[i].t; sz[node]+=sz[edge[i].t]; } } long long huo[600001],yu[600001],tag[600001]={0}; void build(int zuo,int you,int node) { if(zuo==you){huo[node]=yu[node]=rea[zuo];return;} build(zuo,(zuo+you)>>1,node<<1); build(((zuo+you)>>1)+1,you,node<<1|1); huo[node]=huo[node<<1]|huo[node<<1|1]; yu[node]=yu[node<<1]&yu[node<<1|1]; } void pushdown(int zuo,int you,int node) { tag[node<<1]^=tag[node];tag[node<<1|1]^=tag[node]; long long a,b; a=tag[node]&yu[node<<1],b=tag[node]&(man^huo[node<<1]); huo[node<<1]^=a^b;yu[node<<1]^=a^b; a=tag[node]&yu[node<<1|1],b=tag[node]&(man^huo[node<<1|1]); huo[node<<1|1]^=a^b;yu[node<<1|1]^=a^b; tag[node]=0; } long long query(int zuo,int you,int node,int qzuo,int qyou) { if(zuo>qyou||you<qzuo)return 0; if(qzuo<=zuo&&you<=qyou)return huo[node]; pushdown(zuo,you,node); return query(zuo,(zuo+you)>>1,node<<1,qzuo,qyou)|query(((zuo+you)>>1)+1,you,node<<1|1,qzuo,qyou); } void cha(int zuo,int you,int node,int czuo,int cyou,long long val) { if(zuo>cyou||you<czuo)return; if(czuo<=zuo&&you<=cyou) { long long a=val&yu[node],b=val&(man^huo[node]); huo[node]^=a^b;yu[node]^=a^b; tag[node]^=val; return; } pushdown(zuo,you,node); cha(zuo,(zuo+you)>>1,node<<1,czuo,cyou,val); cha(((zuo+you)>>1)+1,you,node<<1|1,czuo,cyou,val); huo[node]=huo[node<<1]|huo[node<<1|1]; yu[node]=yu[node<<1]&yu[node<<1|1]; } inline void ask(int a,int b) { long long jl=0,lc=0; while(lianfa[a]!=lianfa[b]) { if(dep[lianfa[a]]<dep[lianfa[b]])swap(a,b); lc|=query(1,n,1,bh[lianfa[a]],bh[a]);jl+=dep[a]-dep[lianfa[a]]; a=fa[lianfa[a]];jl++; } if(dep[a]>dep[b])swap(a,b); lc|=query(1,n,1,bh[a],bh[b]);jl+=dep[b]-dep[a]; printf("%lld\n",lc*_2[jl]%mod); } inline void bian(int a,int b,long long c) { while(lianfa[a]!=lianfa[b]) { if(dep[lianfa[a]]<dep[lianfa[b]])swap(a,b); cha(1,n,1,bh[lianfa[a]],bh[a],c); a=fa[lianfa[a]]; } if(dep[a]>dep[b])swap(a,b); cha(1,n,1,bh[a],bh[b],c); } int main() { dy(n);dy(m); _2[0]=1;for(int i=1;i<=250000;i++)_2[i]=_2[i-1]*2%mod; int a,b,c,d; for(int i=1;i<n;i++) { dy(a);dy(b); add(a,b);add(b,a); } for(int i=1;i<=n;i++){dy(a);csz[i]=a;} dep[1]=1;dfs1(1);dfs2(1,1); build(1,n,1); while(m--) { dy(a);dy(b);dy(c); if(a==1)ask(b,c); else{dy(d);bian(b,c,d);} } return 0; } ``` 题解已经完了。大家散了吧…… 下面来讲一些扩展内容。 我们可以看到，子异和的完整定义可以表述为“一个集合的所有非空子集中的数的异或和的值之和”。我们发现对于“一个集合的所有非空子集中的数的……的值之和”类的题目都可以用线段树来维护（虽然可能$31$倍常数……）。 首先来个简单的：“一个集合的所有非空子集中的数的乘积的值之和”。假设这个集合为$\{a_1,a_2,…,a_n\}$。我们观察$(a_1+1)(a_2+1)…(a_n+1)-1$这个式子。是不是发现每一个非空子集中的数的乘积都对应着上式展开后的一个单独项？（减一是减去选空集的情况）。维护方法易得。 然后：“一个集合的所有非空子集中的数的与的值之和”。我们用之前分析异或时使用的$t$类来分析。结论其实很好得出：对于目前集合的$t$类表示中的每一位，都等于$2$的**集合中所有数此位上$1$的个数**次方减一。证明过程可以用归纳法证明。当然，这个规律也不是试出来的。类似证明方法，我们分四种情况讨论，分析每一种情况前后两个$s$的某一位之间的关系，得出结论。 当然还有很多很多种情况，大家可以自己试着推一推。总之就是记得要用递推的方法，不要嫌弃找规律。