YbtOJ 891「高斯消元」生日礼物
YbtOJ 891「高斯消元」生日礼物
题目链接：YbtOJ #891
给定一个 n\times m 的矩阵，矩阵的每个位置上有一个灯泡，每个灯泡上有一个开关，一旦按下了位于 (x_0,y_0) 的灯泡的开关， 以及满足 x-x_0=1,y-y_0=2 或 x-x_0=2,y-y_0=1 的位置上的灯泡的开关状态都会改变。
一开始，所有位置上的灯泡都是灭的。
请你求出有多少种方案将所有灯泡都点亮。
由于一个灯泡的开关按两次，本质上是没有按这个开关，因此我们规定每个开关最多按一次。并且按开关的顺序不会影响最终的状态。因此我们规定，两种方案不同，当且仅当存在一个开关，在其中一种方案中被按下，但在另一种方案中没有被按下。
1\leq n,m\leq 600。
Solution
朴素做法
不妨设 a_{x,y} 表示 (x,y) 是否按开关。显然每个灯泡的亮暗同本身与八个方向的开关有关。
也就是说，a_{x,y} 与周围八个方向灯泡的 a 异或和为 1。
对于每个灯泡，我们可以列出这样一个方程组，那么我们就可以得到包含 n\times m 个变量的异或方程组，直接高斯消元后，若自由元个数为 t，则答案为 2^t。
具体过程可以用 bitset 优化，可以做到 O(\frac {n^3m^3}{64})。
删除多余元
目前影响时间复杂度的主要问题在于无用变量过多。这种经典开关问题很显然可以缩减变量规模：
如果我们确定了前两行与最左边一行，那么我们按顺序从上到下从左往右枚举每一个格子 (i,j)，都会因 (i-2,j-1) 格的影响而 唯一确定该格点的开关情况。所以真正未知的元个数为 2m+n-2。（O(n) 级别）
由于最后两行与最后一列没有格子为其灵活变动，是必须固定亮的，所以我们可以对于这些格点列异或方程组，恰与变量个数相同，同样用 bitset 优化即可。
时间复杂度：O(\frac{(n+m)^3}{64})。
Code
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=610,M=N*3,dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,-1,1},P=123456789;
int n,m,cnt,tot,Ans=1,vis[M];
bitset<M> a[N][N],f[M];
I void G(){RI i,j,p;for(i=1;i<=cnt;i++){for(p=0,j=1;j<=cnt;j++) if(f[j][i]&&!vis[j]){p=j;break ;}if(!p) Ans=2LL*Ans%P;else for(vis[p]=1,j=1;j<=cnt;j++) !vis[j]&&f[j][i]&&(f[j]^=f[p],0);}}
int main(){
freopen("present.in","r",stdin),freopen("present.out","w",stdout);
RI i,j,k;for(read(n,m),i=1;i<=min(2,n);i++) for(j=1;j<=m;j++) a[i][j][++cnt]=1;for(i=3;i<=n;i++) a[i][1][++cnt]=1;
for(i=3;i<=n;i++) for(j=2;j<=m;j++) for(a[i][j]=a[i-2][j-1],k=0;k<8;k++)
i-2+dx[k]>=1&&i-2+dx[k]<=n&&j-1+dy[k]>=1&&j-1+dy[k]<=m&&(i-2+dx[k]!=ij-1+dy[k]!=j)&&(a[i][j]^=a[i-2+dx[k]][j-1+dy[k]],0);
for(i=max(1,n-1);i<=n;i++) for(j=1;j<=m;j++) for(f[++tot]=a[i][j],k=0;k<8;k++) i+dx[k]>=1&&i+dx[k]<=n&&j+dy[k]>=1&&j+dy[k]<=m&&(f[tot]^=a[i+dx[k]][j+dy[k]],0);
for(i=max(0,n-2);i;i--) for(f[++tot]=a[i][m],k=0;k<8;k++) i+dx[k]>=1&&i+dx[k]<=n&&m+dy[k]>=1&&m+dy[k]<=m&&(f[tot]^=a[i+dx[k]][m+dy[k]],0);
return G(),writeln(Ans),0;
}腾讯云开发者
