状压DP，以前这题TLE，改了好久才改好（还不如重写QAQ）
1 //#include<bits/stdc++.h> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 #include<queue> 7 #define inc(i,l,r) for(int i=l;i<=r;i++) 8 #define dec(i,l,r) for(int i=l;i>=r;i--) 9 #define link(x) for(edge *j=h[x];j;j=j->next) 10 #define mem(a) memset(a,0,sizeof(a)) 11 #define inf 1e9 12 #define ll long long 13 #define succ(x) (1<<x) 14 #define NM 13 15 using namespace std; 16 int read(){ 17 int x=0,f=1;char ch=getchar(); 18 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 19 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 20 return x*f; 21 } 22 ll d[NM+1][succ(NM)]; 23 int n,m,x,s; 24 bool c[succ(NM)]; 25 bool check(int x,int y){ 26 return (x|y)==s&&c[x&y]; 27 } 28 int main(){ 29 n=succ(13)-1; 30 inc(i,0,n){ 31 x=0;c[i]=true; 32 inc(j,0,12) 33 if(i&succ(j))x++; 34 else{ 35 if(x%2)c[i]=false; 36 x=0; 37 } 38 } 39 while(1){ 40 n=read();m=read(); 41 if(n==0||m==0)break; 42 if(n>m)swap(n,m); 43 mem(d); 44 s=succ(n)-1; 45 inc(t,0,s){ 46 d[1][t]=c[t]; 47 // printf("%d ",d[1][t]); 48 } 49 // printf(" "); 50 inc(i,2,m){ 51 inc(t,0,s){ 52 inc(v,0,s) 53 if(check(t,v)) 54 d[i][t]+=d[i-1][v]; 55 // printf("%d ",d[i][t]); 56 } 57 // printf(" "); 58 } 59 printf("%lld ",d[m][s]); 60 } 61 return 0; 62 }