《莫涛 高斯消元解xor方程组》由会员分享，可在线阅读，更多相关《莫涛 高斯消元解xor方程组（49页珍藏版）》请在金锄头文库上搜索。
1、XOR方程组清华大学 莫涛 hwdhwd.name前言约定lXOR的计算方式lN,M=k使得Aj,i为1则交换第j行与第k行用第k行对之后的行进行消元k = k + 1l否则第个变量是自由变量，k不变l时间复杂度O(NM2)解的判断l无解l存在方程系数全为0，常数项不为0l唯一解l无自由变量l多解：l出现了S个自由变量，这些变量可任意取值从而确 定其余变量的值l2S组解例子lN = 4 K = 7lN个数为 5 6 3 4lX1 + X3 = 1lX2 + X3 = 1lX1 + X2 + X4 = 1l欢迎上台解方程位运算优化l一个int64/long long储存60个bitl取出X的第
2、i位：X and 2i-1l两行做异或：A xor B例五l在例四的基础上，给定M个限制，每个限制是 那N个数的一个子集，要求该子集中的数恰有 奇数个或偶数个被选择。解法l给每个限制添加一个方程l用例四的方法解决例六l从N个数中选出任意个数，使XOR和最大。lO(N*603)? O(N*602)? (N/60)*602)?O(N*60)?l最简洁的算法？解法一l从高到低确定K的每一位，设当前考虑第i位l若Ki = 1可行则确定l否则Ki = 0l判断可行l对前i位列方程，使用例四的方法l时间复杂度O(N*603)解法二l确定第i位时，前面的方程已经消好元了l只需用前i-1个方程对第i个方程进行
3、消元l例：前方程组中添加X1 + X2 + X3 + X4 = 0l时间复杂度O(N*602)l使用位运算可以优化为O(N/60)*602)解法三l从前到后考虑每一个数，若它可被之前的数凑 出则可以直接将其扔掉l维护已有的独立数的上三角矩阵，相当于将A 旋转90度后进行高斯消元l直接确定最终答案，O(N*60)例七l从N个数中选出任意个数，求能得到的XOR和 的种数。解法l利用例六的解法三l设有T个独立数，答案为2Tl为什么不会有重复？l其它解法？l建议学习线性代数相关知识例八l从N个数中选出任意个数，使它们的XOR和与 K的XOR和最大。解法l例六解法三，直接确定答案概览二（十分钟）lN个点
4、M条边的边带权的无向图，把点分成两个集合，使处于两集合 之间的边的XOR和最大。（提示：1,2,5,10,20,50,100。7种币值可凑 出所有面值）lN个点M条边的边带权的无向图，求一个回路使XOR和最大。l用第5题的思路。l方程的解与回路一一对应吗？证明之。l时间复杂度？l用第9题的思路。l最少需要多少种“币值”？证明之。l如何构造这样一组“币值”。l上一题的makedata怎么写？lN个点M条边的边带权的无向图，求一条1号点到N号点的路径，使 XOR和最大。例九（XOR最大割）lN个点M条边的边带权的无向图，把点分成两 个集合，使处于两集合之间的边的XOR和最大 。l提示：1,2,5,
5、10,20,50,100。7种币值可凑出所 有面值。解法l设hi为i的邻边的XOR和l一个割S,T = hi(i在S中) = hi(i在T中) l转化为例六例十（XOR最大环）lN个点M条边的边带权的无向图，求一个回 路使XOR和最大。l用第5题的思路。l方程的解与回路一一对应吗？证明之。l时间复杂度？l用第9题的思路。l最少需要多少种“币值”？证明之。l如何构造这样一组“币值”。解法一lXi表示第i条边是否在路径中l点的邻边中恰有偶数条被取lN个方程，M个变量方程的解与回路的对应性l回路均满足方程l方程的解可能是若干不连通的回路l走过来再走回去，XOR和不变时间复杂度l转化为例五+例六l只能
6、使用解法二lO(M/60)N(N+60)解法二l两个回路的和仍是回路l和 指 异或和/对称差l连通性问题l结论：一个无向连通图G中有且仅有M-N+1个 独立回路。数学归纳法lM=N-1时，树，结论成立l设M=K时结论成立，当M=K+1时，任取G中一 条边e，G-e中有K-N+1个独立回路，且l任取一个包含e的回路C，显然独立于之前的回路l任意两个包含e的回路C1与C2，C12=C1+C2是G-e的 回路，C2不独立l故能且仅能增加一个包含e的独立回路l从而G中恰有(K+1)-N+1个独立回路，证毕构造法l任取原图一棵生成树Tl对于每条不在T中的边e，取T+e的回路时间复杂度l利用构造法，求出M
7、-N+1个独立回路的XOR和l转化为例六lO(M+N)*60)l建议学习图论相关知识例十一l例十的makedata怎么写？解法l生成一个独立数集l随机生成一棵树的边权l对于每条非树边，确定其值使得该边对应的环 的XOR和可由独立数集生成例十二（XOR最长路）lN个点M条边的边带权的无向图，求一条1号点 到N号点的路径，使XOR和最大。解法l任意两条路径的和为一个环l任取一条1-N的路，找一个环与其XOR和最大l转化为例八例十三l扩展思考：从N个数中选出不超过K个，使 XOR和最大。例十四l扩展思考：在第10题基础上，限制求得的回路 是简单回路。例十五l扩展思考：带权二分图，求一个完美匹配，使
8、XOR和最大。Matrixl一个N*N的01矩阵，每个十字中有偶数个1l已经填好了M个数，求填完该矩阵的方案数lM=N=1000解法l确定第一行后，可以递推确定剩下的格子，且 该方案合法当且仅当这样递推得出的第N+1行 全是0l第一行的N个格子作为未知数l递推求出第N+1行与第1行的关系，N个方程l已填数的信息，M个方程l该方程组的解数即为答案，O(N3/60)POI2005dwal一个无向图，将N个点分成两个点集，使得尽 量多的点满足：l邻居中有偶数个点和自己在同一集合l允许分出空集lN=1000解法l设点i的邻居为Si，Si中有偶数个点与i同集合l若di为奇，Si中两集合均包含偶数个点l若di为偶，Si+i中两集合均包含奇数个点lXi表示第i个数所属的集合（0或1）lN个未知数，N个方程l猜想：该方程组一定有解，即答案为N证明l见Matrix67的Blog谢谢
