- T1爆搜 #include <bits/stdc++.h> using namespace std; #define maxn 100 #define maxm 5600 int n; bool vis[maxm]; inline int read_() { int x_=0,f_=1;char c_=getchar(); while(c_<'0'||c_>'9') {if(c_=='-') f_=-1;c_=getchar();} while(c_>='0'&&c_<='9') {x_=(x_<<1)+(x_<<3)+c_-'0';c_=getchar();} return x_*f_; } bool dfs_(int S) { if( !S ) return true; if( vis[S] ) return false; int u = S & 1,pdc; if( u == 1 ) { // 变为0 pdc = S >> 1; vis[S] = true; if( dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; // 不变 pdc = ( S >> 1 ) + ( 1 << ( n - 1 ) ); vis[S] = true; if( dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; } else { // 变为1  pdc = ( S >> 1 ) + ( 1 << ( n - 1 ) ); vis[S] = true; bool flag = dfs_(pdc); vis[S] = false; // 不变 pdc = ( S >> 1 ); vis[S] = true; if( flag && dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; } return false; }  int main() { //freopen("a.txt","r",stdin); scanf("%d",&n); int AKIOI = 0; for(int S = 0;S < ( 1 << n );++S) { memset(vis,false,sizeof(vis)); if( dfs_(S) ) ++AKIOI; } printf("%d",AKIOI); return 0; }