YbtOJ 891「高斯消元」生日礼物

(Updated: )
oi
,

题目链接：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})$。

删除多余元

目前影响时间复杂度的主要问题在于无用变量过多。这种经典开关问题很显然可以缩减变量规模：

image.png

如果我们确定了前两行与最左边一行，那么我们按顺序从上到下从左往右枚举每一个格子 $(i,j)$，都会因 $(i-2,j-1)$ 格的影响而 唯一确定该格点的开关情况。所以真正未知的元个数为 $2m+n-2$。（$O(n)$ 级别）

由于最后两行与最后一列没有格子为其灵活变动，是必须固定亮的，所以我们可以对于这些格点列异或方程组，恰与变量个数相同，同样用 bitset 优化即可。

时间复杂度：$O(\frac{(n+m)^3}{64})$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}