传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5998
经典的开关灯问题，学习到了著名的(但我不知道的)做法
显然如果我们确定了矩阵距离边缘长为5的的那些块的状态，那么整个矩阵也就确定了
所以要想找自由元只需要在这些20*n个点里找就没了
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #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;} |
hack:
1
5 5 5
2 2
-1 -3
4 -2
2 2
-4 2
嗯……非常抱歉……我人脑无法处理这组数据……
我觉得问题可能出在那两个2 2 上？
如果有标程的话请联系我 ^_^ 谢谢