用高斯消元法求有效方程个数.Pascal的要在旁边写解释就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.看NOI1996那道灯塔的题吧

Question

用高斯消元法求有效方程个数.Pascal的要在旁边写解释
就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.
看NOI1996那道灯塔的题吧

Answer 1

经典问题啊.帮你找了这些,希望能帮上忙
设b[i,j]表示灯塔转状态.我们不难发现b[i,j]=(b[i+1,j]+b[i+1,j+1]) mod 2
继续展开,b[i,j]=(b[i+2,j]+2b[i+2,j+1]+b[i+2,j+2]) mod 2
=(b[i+3,j]+3b[i+3,j+1]+3b[i+3,j+2]+b[i+3,j+3]) mod 2
=(a[1]b[n,1]+a[2]b[n,2]+……+a[n]b[n,n]) mod 2
这样,对于每一个已知的灯状态,我们都可以用最底层灯的状态来表示,既把最底层的灯状态设为未知数,对于每一个已知的灯状态,我们都可以列一个方程.
而对于方程中每个未知数的系数不难发现是符合杨辉三角的.
这样,我们可以得到一个方程组.
要求解的个数,用高斯消元法求出方程组的有效方程个数m,则解的个数是2n-m.
由于本题的每个未知数只能取0或1,而最后的结果要mod 2,所以系数只有奇偶之分,1表示奇数,0表示偶数（即每个系数mod 2）.
而在消元过程中,我们也只需考虑奇偶,即系数任意时刻只可能是0或1,这样用xor就可以了.