這道題題意是：
有N盞燈，每個(gè)燈有兩個(gè)狀態(tài)：開、關(guān)。有4個(gè)按鈕，第一個(gè)按鈕使得所有燈改變狀態(tài)，第二個(gè)按鈕使得奇數(shù)號(hào)燈改變狀態(tài)，第三個(gè)按鈕使得偶數(shù)號(hào)燈改變狀態(tài)，第四個(gè)按鈕使得3K+1號(hào)燈改變狀態(tài)。
開始所有燈都是亮著的，給出操作次數(shù)，最后亮著的燈和滅了的燈，求最后所有可能的狀態(tài)。
這題可以用模二方程組來表示。設(shè)a、b、c、d分別為第一個(gè)、第二個(gè)、第三個(gè)、第四個(gè)按鈕按過的次數(shù)。count為操作總數(shù)，滿足：
如第k盞燈亮著
如k%2==1&&(k-1)%3==0，則(a+b+d)%2=0
如k%2==1&&(k-1)%3==1，則(a+b)%2=0
如k%2==0&&(k-1)%3==0，則(a+c+d)%2=0
如k%2==0&&(k-1)%3==1，則(a+c)%2=0
如第k盞燈滅著
如k%2==1&&(k-1)%3==0，則(a+b+d)%2=1
如k%2==1&&(k-1)%3==1，則(a+b)%2=1
如k%2==0&&(k-1)%3==0，則(a+c+d)%2=1
如k%2==0&&(k-1)%3==1，則(a+c)%2=1
開始想用高斯消元來處理這個(gè)方程組，后來一看變量只有4個(gè)。。而且是模二關(guān)系下的方程組，直接枚舉即可，總狀態(tài)數(shù)不過16種。然后構(gòu)造解并hash判重即可。
代碼如下：
1
import java.io.*;
2import java.util.*;
3
public class Main 
{
4
5
/** *//**
6 * @param args
7
*/
8 static int n=0,co=0,flag[]=new int [10];
9 static char res[];
10 static TreeSet<String> ans=new TreeSet<String>();
11 static void makeans(int a,int b,int c,int d,int pos)
12 {
13 if(pos>n)
14 {
15 ans.add(new String(res));
16 }
17 else
18 {
19 if(pos%2==1)
20 if((pos-1)%3==0)
21 res[pos-1]=(char)((a+b+d+1)%2+48);
22 else
23 res[pos-1]=(char)((a+b+1)%2+48);
24 else
25 if((pos-1)%3==0)
26 res[pos-1]=(char)((a+c+d+1)%2+48);
27 else
28 res[pos-1]=(char)((a+c+1)%2+48);
29 makeans(a,b,c,d,pos+1);
30 }
31 }
32 public static void main(String[] args) throws IOException{
33 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
34 in.nextToken();
35 n=(int)in.nval;;
36 in.nextToken();
37 co=(int)in.nval;
38 Arrays.fill(flag,-1);
39 flag[0]=co&1;
40 res=new char[n];
41 while(true)
42 {
43 in.nextToken();
44 if((int)in.nval==-1) break;
45 int t=(int)in.nval;
46 if((t&1)==1)
47 if((t-1)%3==0)
48 flag[3]=0;
49 else
50 flag[1]=0;
51 else
52 if((t-1)%3==0)
53 flag[4]=0;
54 else
55 flag[2]=0;
56 }
57 while(true)
58 {
59 in.nextToken();
60 if((int)in.nval==-1) break;
61 int t=(int)in.nval;
62 if((t&1)==1)
63 if((t-1)%3==0)
64 flag[3]=1;
65 else
66 flag[1]=1;
67 else
68 if((t-1)%3==0)
69 flag[4]=1;
70 else
71 flag[2]=1;
72 }
73 for(int a=0;a<=1;a++)
74 for(int b=0;b<=1;b++)
75 for(int c=0;c<=1;c++)
76 for(int d=0;d<=1;d++)
77 {
78 if(a+b+c+d>co) continue;
79 if(((a+b+c+d)&1)!=flag[0]) continue;
80 if(flag[1]!=-1&&((a+b)&1)!=flag[1]) continue;
81 if(flag[2]!=-1&&((a+c)&1)!=flag[2]) continue;
82 if(flag[3]!=-1&&((a+b+d)&1)!=flag[3]) continue;
83 if(flag[4]!=-1&&((a+c+d)&1)!=flag[4]) continue;
84 makeans(a,b,c,d,1);
85 }
86 for(String p:ans)
87 System.out.println(p);
88 }
89
90
}
91