hdu5998 jvjhfhg loves Magic Tower

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5998

经典的开关灯问题,学习到了著名的(但我不知道的)做法

显然如果我们确定了矩阵距离边缘长为5的的那些块的状态,那么整个矩阵也就确定了
所以要想找自由元只需要在这些20*n个点里找就没了

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int n,m,k;
int dx[10],dy[10];
int mp[maxn][maxn];
long long pw(long long x,long long k){
	long long mo=1e9+7;
	long long ans=1;
	for(;k;k>>=1){
		if(k&1)ans=ans*x%mo;
		x=x*x%mo;
	}
	return ans;
}
bitset<2000>base[2000];
int N;
bool insert(bitset<2000>bs){
	for(int i=N;i>=0;i--)if(bs[i]){
		if(base[i].any()){
			bs=bs^base[i];
		}else{
			base[i]=bs;
			return true;
		}
	}
	return false;
}


int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=0;i<k;i++)
			cin>>dx[i]>>dy[i];
		N=0;
		memset(mp,0,sizeof mp);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i<=5||i>=n-4||j<=5||j>=m-4){
					mp[i][j]=++N;
				}
			}
		}
		
		for(int i=0;i<=N;i++)
			base[i].reset();
		int cnt=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)if(mp[i][j]){
				bitset<2000>bs;
				bs[mp[i][j]]=1;
				bs[0]=1;
				for(int l=0;l<k;l++){
					int x=i+dx[l];
					int y=j+dy[l];
					if(x<1||x>n||y<1||y>m)continue;
					if(mp[x][y])
						bs[mp[x][y]]=bs[mp[x][y]]^1;
				}
				if(!insert(bs))
					cnt++;
			}
		}
		long long ans=pw(2,cnt);
		cout<<ans<<endl;
	}
	return 0;
}

2 thoughts to “hdu5998 jvjhfhg loves Magic Tower”

    1. 嗯……非常抱歉……我人脑无法处理这组数据……
      我觉得问题可能出在那两个2 2 上?
      如果有标程的话请联系我 ^_^ 谢谢

发表评论

电子邮件地址不会被公开。 必填项已用*标注