莫涛-高斯消元解XOR方程组

XOR方程组清华大学莫涛[e-mail]@hwd.name前言约定XOR的计算方式N,M=100000数字为260内的非负整数讨论某道题时，假设其之前所有例题已解决概览一（10分钟）证明XOR满足交换律，结合律，是自身的逆运算。从N个数中选出两个数，使XOR和最大。N个点的边带权的树，找一条路径使XOR和最大。从N个数中选出若干个，使XOR和为X，给出方案或指出不可行。在上题的基础上，给定M个限制，每个限制是那N个数的一个子集，要求该子集中的数恰有奇数个或偶数个被选择从N个数中选出任意个数，使XOR和最大。O(N*643)?O(N*642)?O((N/64)*642)?O(N*64)?从N个数中选出任意个数，求能得到的XOR和的种数。从N个数中选出任意个数，使它们的XOR和与X的XOR和最大。例一证明XOR满足交换律，结合律，是自身的逆运算。XOR关于每一位的独立性。二进制数比较大小时从高到低。例二从N个数中选出两个数，使XOR和最大。解法枚举一个数，查找最接近的数构造二进制树[0000][11111][00][11][000][11][11][0][1][111][0][1][0][1][1][0][0][11][0][1]与0111最接近的是1010O(60N)例三N个点的边带权的树，找一条路径使XOR和最大。解法任选根，hi表示从根到i的路径的XOR和X到Y的路径的XOR和等于hxxorhy转化为例二例四从N个数中选出若干个，使XOR和为K，给出方案或指出不可行。解法Xi=0示第i个数不选，Xi=1表示选考虑K的p位若是1，则第p个二进制位为1的数字有奇数个被选否则偶数个被选择得到方程Xi1+Xi2+……+Xis=Kp(‘+’为异或)联立60个方程，方程的解等价于原问题的解高斯消元设N个未知数，M个方程，A为系数矩阵k=1fori=1toN若存在j=k使得Aj,i为1则交换第j行与第k行用第k行对之后的行进行消元k=k+1否则第ｉ个变量是自由变量，k不变时间复杂度O(NM2)解的判断无解存在方程系数全为0，常数项不为0唯一解无自由变量多解：出现了S个自由变量，这些变量可任意取值从而确定其余变量的值2S组解例子N=4K=7N个数为5634X1+X3=1X2+X3=1X1+X2+X4=1欢迎上台解方程位运算优化一个int64/longlong储存60个bit取出X的第i位：Xand2i-1两行做异或：AxorB例五在例四的基础上，给定M个限制，每个限制是那N个数的一个子集，要求该子集中的数恰有奇数个或偶数个被选择。解法给每个限制添加一个方程用例四的方法解决例六从N个数中选出任意个数，使XOR和最大。O(N*603)?O(N*602)?((N/60)*602)?O(N*60)?最简洁的算法？解法一从高到低确定K的每一位，设当前考虑第i位若Ki=1可行则确定否则Ki=0判断可行对前i位列方程，使用例四的方法时间复杂度O(N*603)解法二确定第i位时，前面的方程已经消好元了只需用前i-1个方程对第i个方程进行消元例：前方程组中添加X1+X2+X3+X4=0时间复杂度O(N*602)使用位运算可以优化为O((N/60)*602)解法三从前到后考虑每一个数，若它可被之前的数凑出则可以直接将其扔掉维护已有的独立数的上三角矩阵，相当于将A旋转90度后进行高斯消元直接确定最终答案，O(N*60)例七从N个数中选出任意个数，求能得到的XOR和的种数。解法利用例六的解法三设有T个独立数，答案为2T为什么不会有重复？其它解法？建议学习《线性代数》相关知识例八从N个数中选出任意个数，使它们的XOR和与K的XOR和最大。解法例六解法三，直接确定答案概览二（十分钟）N个点M条边的边带权的无向图，把点分成两个集合，使处于两集合之间的边的XOR和最大。（提示：1,2,5,10,20,50,100。7种币值可凑出所有面值）N个点M条边的边带权的无向图，求一个回路使XOR和最大。用第5题的思路。方程的解与回路一一对应吗？证明之。时间复杂度？用第9题的思路。最少需要多少种“币值”？证明之。如何构造这样一组“币值”。上一题的makedata怎么写？N个点M条边的边带权的无向图，求一条1号点到N号点的路径，使XOR和最大。例九（XOR最大割）N个点M条边的边带权的无向图，把点分成两个集合，使处于两集合之间的边的XOR和最大。提示：1,2,5,10,20,50,100。7种币值可凑出所有面值。解法设hi为i的邻边的XOR和一个割{S,T}=∑hi(i在S中)=∑hi(i在T中)转化为例六例十（XOR最大环）N个点M条边的边带权的无向图，求一个回路使XOR和最大。用第5题的思路。方程的解与回路一一对应吗？证明之。时间复杂度？用第9题的思路。最少需要多少种“币值”？证明之。如何构造这样一组“币值”。解法一Xi表示第i条边是否在路径中点的邻边中恰有偶数条被取N个方程，M个变量方程的解与回路的对应性回路均满足方程方程的解可能是若干不连通的回路走过来再走回去，XOR和不变时间复杂度转化为例五+例六只能使用解法二O((M/60)N(N+60))解法二两个回路的和仍是回路‘和’指‘异或和’/‘对称差’连通性问题结论：一个无向连通图G中有且仅有M-N+1个独立回路。数学归纳法M=N-1时，树，结论成立设M=K时结论成立，当M=K+1时，任取G中一条边e，G-e中有K-N+1个独立回路，且任取一个包含e的回路C，显然独立于之前的回路任意两个包含e的回路C1与C2，C12=C1+C2是G-e的回路，C2不独立故能且仅能增加一个包含e的独立回路从而G中恰有(K+1)-N+1个独立回路，证毕构造法任取原图一棵生成树T对于每条不在T中的边e，取T+e的回路时间复杂度利用构造法，求出M-N+1个独立回路的XOR和转化为例六O((M+N)*60)建议学习《图论》相关知识例十一例十的makedata怎么写？解法生成一个独立数集随机生成一棵树的边权对于每条非树边，确定其值使得该边对应的环的XOR和可由独立数集生成例十二（XOR最长路）N个点M条边的边带权的无向图，求一条1号点到N号点的路径，使XOR和最大。解法任意两条路径的和为一个环任取一条1-N的路，找一个环与其XOR和最大转化为例八例十三扩展思考：从N个数中选出不超过K个，使XOR和最大。例十四扩展思考：在第10题基础上，限制求得的回路是简单回路。例十五扩展思考：带权二分图，求一个完美匹配，使XOR和最大。Matrix一个N*N的01矩阵，每个十字中有偶数个1已经填好了M个数，求填完该矩阵的方案数M=N=1000解法确定第一行后，可以递推确定剩下的格子，且该方案合法当且仅当这样递推得出的第N+1行全是0第一行的N个格子作为未知数递推求出第N+1行与第1行的关系，N个方程已填数的信息，M个方程该方程组的解数即为答案，O(N3/60)POI2005dwa一个无向图，将N个点分成两个点集，使得尽量多的点满足：邻居中有偶数个点和自己在同一集合允许分出空集N=1000解法设点i的邻居为Si，Si中有偶数个点与i同集合若di为奇，Si中两集合均包含偶数个点若di为偶，{Si+i}中两集合均包含奇数个点Xi表示第i个数所属的集合（0或1）N个未知数，N个方程猜想：该方程组一定有解，即答案为N证明见Matrix67的Blog谢谢