用高斯消元法求有效方程个数.Pascal的要在旁边写解释就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.看NOI1996那道灯塔的题吧
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 09:29:11
用高斯消元法求有效方程个数.Pascal的要在旁边写解释就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.看NOI1996那道灯塔的题吧
用高斯消元法求有效方程个数.Pascal的要在旁边写解释
就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.
看NOI1996那道灯塔的题吧
用高斯消元法求有效方程个数.Pascal的要在旁边写解释就是已知一些方程要你找出有多少个有效的方程.也就是去掉重复的.看NOI1996那道灯塔的题吧
经典问题啊.帮你找了这些,希望能帮上忙
设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就可以了.