OI中的线性代数
OI中的线性代数
线性基
Example1
给定\(n\)个非平方因子数\(a_i\),求有多少种选取一个子集的方式满足每个质因子都在子集中恰好出现偶数次.\(n\leq 2\times 10^5,a_i\leq 10^6\).
考虑将每个数的质因子压成一个二进制数,那所求也就是问有多少种选取子集的方式使得子集内二进制数异或和为\(0\).自然想到线性基.\(2\)的自由变量的数量次幂即答案.
但是直接做线性基不太对,因为质数级别是\(10^6\).我们冷静一下,把一个数中大于\(1000\)的质因子拿出来,显然只会有一个.把所有数字根据这个质因子分类,那么显然一个组内必能插入一个数(作为这个质因子的主元),而其他数也必要异或上这个数,而异或后就只有小于等于\(1000\)的质因子了,这种质因子只有不到\(200\)个,可以拿bitset优化一下.
复杂度\(O(\cfrac{\pi(\sqrt a)^2n}{w})\).
Example2([CF1100F]Ivan and Burgers)
考虑扫描线,这样我们需要解决如何询问一段后缀\([l,n]\)的答案,以及如何根据上一个位置的后缀推出这一个位置的后缀.
考虑有一个暴力是直接把每个后缀的线性基建出来:注意在此过程中,能放到高位的数字一定出现地尽可能靠后,因为它一早就被放进来了.而只要满足这个条件,也就是能放高位的一定尽量放高位,并且高位出现时间要尽可能晚,那我们自然就得到了此时的线性基,删去那些出现太靠前的数字就行.
但有没有什么直接一点的理解方式呢?一个直觉是,我们现在要把出现时间太早的给删了,那肯定想要让高位出现时间尽可能晚.但是这样会有两个问题:
- 可能\(l\)较小但是没那么小,高位即使不顶替,也会被选上,但是顶替了高位就无法顶替一个将被删除的低位.
- 由于线性基并非最简线性基,我们最后的答案有可能不会将某一位异或进答案,那此时尽量最优化它是不优秀的.
- 线性基中的元素不能受到非线性基中的元素的影响,我们删除一位的时候,这一位有可能在之前影响了比它低的一些位置.
来一个一个解决.
(3)是最好解决的.对于因为出现时间太早而导致的删除来说,因为如果一个位置被高位影响了,根据我们的构造过程,这个位置出现时间必然不会晚于那个高位,高位都被删了,那这个位置也会被删.
对于因为被其他人而取代导致的删除来说,因为它被删了,因此它一定可以表示为其它线性基底的异或,因此有影响也无所谓.
再来看(1),考虑我们当前插入的数字是\(v\),如果\(v\)本来就会被加入线性基,那它扔到高位,然后替换下来的那个数字也不可能被删除,一定会延续到低位.如果\(v\)本来不会被加入,必然因为有一些基底的异或值是\(v\),那么把\(v\)加入后,一路到最后,被删除的那个基底必然是出现时间最早的那个菜逼,删了就是了.
接下来是(2),考虑上面这个过程完全不耽误你把它变成最简线性基,最简线性基就没这个问题了.
当然这题还可以分治,注意到用线段树直接合并区间的线性基的复杂度达到了\(\log^3\),但是如果我们用猫树的结构但是不必要在线,复杂度降到了\(\log^2\).
Example3(luoguP8337 [Ynoi2004] rsxc)
注意到区间数字种类个数一定是二的整数次幂,假设为\(2^k\),先枚举\(k\).
首先根据CF1100F,我们可以离线找出区间的线性基,这意味着区间不同整数个数是否是\(2^k\).
做完这两步之后呢?我们接下来需要求和.这里注意到随着扫描线的进行,左端点可能合法的区间左右端点均单调不降,我们对着二维坐标系做一个差分(就是把一条直线延伸到\(y=x\)这条直线上),于是可以\(O(1)\)求和.
这里详细解释一下上面的那个套路:当我们插入一个数字的时候,每当遇到了一个此位置是\(1\)的出现次数早于该数字的数字,我们就交换它们.为啥这样是对的呢?首先如果插入的这个数字并不能被其他数字所表示,那无论怎么交换都不会有影响.而如果可以,那一定会与所有参与表示的数字都交换一次.注意到每次交换等价于找到两者中出现较早的那个,所以最后一定会删去出现最早的数字.
Example4([uoj703]赵云八卦阵)
用一下构造能力不难发现,每个点的取值是它前面的数能表示出的所有数(也就是线性基)异或上他自己.
我们考虑从左往右加线性基(并保存旧的版本),每次如果一个数并不能更新线性基,说明这个数字能取的取值范围就是到它的线性基中的所有数字.进一步地,你注意到它的取值范围一定包括了它前面的所有数字,这个同样可以通过线性基的性质来得到.
注意到难点在于那些加入后更新线性基的点,称它们为关键点,这样的关键点最多\(\log V\)个.所以我们可以暴力讨论它们的存在.而那些普通的点显然分成了若干个段,每段的取值是相等的.我们可以按照线性基的顺序走.如果我们必须要在关键点和其它的点中挑一个删了,显然我们要删关键点,因为其他的点能很完美地接上,但是关键点可不一定能接上.
也就是说对于一个非关键点,能选则一定要选.因此我们直接从后往前dp,如果遇到关键点的话讨论一下它选不选,遇到非关键点一定要选,如果选不了就更新答案.
我们不妨设计一个dp,设\(f_{i,j}\)表示从\(n\)走到第\(i\)个数字,中间取了\(j\)个关键点,\(a_i\)的最大值是多少.这样问题转化为:
- 对于一个数字\(X\),找到线性基中最大的小于它的数字.
- 对于一个数字\(X\),将它与线性基中若干基底异或得到\(X'\),使得\(X'<Y\)并且\(X'\)尽可能大.
不难发现第一个问题就是第二个问题中的\(X=0,Y=X\)的情况.用最简线性基算排名可以轻松解决上面的问题.
杂题
Example1([CF1270I]Xor on Figures)
首先我们发现,它的平移操作和矩阵很相似,我们考虑将操作写成矩阵形式.
具体地,我们定义新的矩阵乘法为:\(A\times B=C\),其中\(C_{x,y}=\bigoplus_{i=0}^{2^k-1}\bigoplus_{j=0}^{2^k-1}A_{i,j}\times B_{(x-i)\mod 2^k,(y-j)\mod 2^k}\).
定义矩阵\(F\):\(F_{x_i,y_i}=1,1\leq i\leq t\),其他位置均为\(0\).不难发现每次操作无非是将\(F\)乘上一个只有\((X,Y)\)位置是\(w\),其余位置都是\(0\)的矩阵然后异或到\(A\)上.我们发现这些操作也可以压缩成一个矩阵.这样问题就转化为:我们已知\(F\),求\(0\)的位置尽可能多的矩阵\(C\),满足\(F\times C=A\).
我们看到这个形式,发现它很优美,这个时候自然有一个猜想:\(F\)在这种形式下是否存在逆矩阵呢?
注意到\(F\)的值是异或运算下,和取膜有一定关系,我们再大胆猜测:\(\exists m,F^m=I\),其中\(I_{0,0}=1\),其他位置都是\(0\).此时\(F^{-1}=F^{m-1}\).打表可以发现\(m=2^k\).
接下来我们只需要证明这个结论就行.其实也好证:注意到进行一次运算后,\(F_{x_i,y_i}\times F_{x_j,y_j}\)和\(F_{x_j,y_j}\times F_{x_i,y_i}\)都会更新到\(F^2_{x_i+x_j,y_i+y_j}\),因此他们俩互相抵消.这意味着\(F^2\)中,只有\(F^2_{2x_i,2y_i}\)有可能非零.
进行\(2^k\)后,由于下标对\(2^k\)取膜,容易发现这个时候只有\((0,0)\)有可能非零.而由于一共有奇数个\(1\),所以这里一定是\(1\).得证.有\(C=F^{2^k-1}A\).
根据上面的证明过程不难发现,\(F\)的\(2\)的整次幂很好求,所以我们拆开幂,有\(C=\prod_{i=0}^{k-1}F^{2^i}A\).注意到\(F\)很稀疏,最多只有\(t\)个地方非零,所以做一次的复杂度是\(O((2^k)^2t)\),总复杂度\(O(kt4^k)\).
Example2([Petrozavodsk Winter-2014. Moscow SU Tapir Contest(openstrain contest 1435) F]Passing Finals)
给定一个\(n\times n\)的矩阵,其中有\(m\)个位置(\(m\leq 5\))的数字缺失了.给定质数\(P\),现在要在这\(m\)个位置上填上\([0,p-1]\)的数字,使得最后矩阵的行列式在\(\bmod p\)意义下等于给定数字\(C\),求任意一组方案,\(1\leq n\leq 100\),\(2\leq P\leq 10^9\).
如果\(m=1\),做代数余子式展开,显然如果这个位置对应的代数余子式为\(0\),那它填什么无所谓,随便填一个然后验证.不然,我们一定可以用逆元算出一个答案,使得满足条件.
同理,如果\(m>1\),我们考虑随机\(m-1\)个位置并随机它们的值,然后验证.如果我们能找到一组随机满足剩下的那个位置对应的代数余子式非零就做完了.如果我们随机了若干次,还是没有找到,宣告无解.
逆矩阵求解线性方程组
如果我们已知线性方程组的系数矩阵,但是多次询问,每次会给出不同的常数项,我们可以使用下文中提到的逆矩阵来求解.
Example1(codeforces CF1266H Red-Blue Graph)
如果我们设\(x_i\)表示每个点被经历过多少次.注意到一共有\(n-1\)个方程以及\(n-1\)个未知数,我们实际上是要根据\(s\)和\(v\)求出一组\(x\)然后判定合法,我们先写方程: \[ x_i-[i=1]\\=\sum_{e:j\rightarrow i \ is\ blue}\frac{x_j-[s_e=red]-[j=v]}{2}\\+\sum_{e:j\rightarrow i \ is\ red}\frac{x_j+[s_e=red]-[j=v]}{2} \] 化简一下: \[ 2x_i-\sum_{j\rightarrow i}x_j=-\sum_{e:j\rightarrow i \ is\ blue}[s_e=red]+\sum_{e:j\rightarrow i \ is\ red}[s_e=red]-\sum_{j\rightarrow i}[j=v]+2[i=1] \] 注意到这是一个系数恒定且常数项不确定的矩阵,可以先矩阵求逆再做.
另外有一个问题是,怎么证明这个系数矩阵一定存在逆矩阵,不难注意到这是个基尔霍夫矩阵,显然$$为\(0\).
这也就是说,我们一定可以求出唯一一组解.我们要做的只是判定它是否合法.
先通过数学归纳等方法证明一组满足流量平衡以及以下条件的\(x,s,v\)一定合法:
对于任意一个点,都存在一条只经过激活边的路径到达最终点.
首先充分性,如果满足这个条件,我们只要不断地退流就可以得到一组一定合法的答案.
然后必要性,如果存在一个点没有这条路径,那这个点也必然不可能被回溯到,自然不可能出现一组解.
这题关键在于发现流量平衡这个等价条件,然后知道我们可以求出一组状态,并只需要判定状态是否合法,找判定条件.
然后写分数的人被卡常了,泪目.