SRM449 div1 medium
頑張った。long long をintに変えるとちょっと実行時間が短くなる。
#include <vector> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; int offset=8; int cache[17+5][(1<<17)]; class HexagonalBattlefield { public: int N; int field[17+5][17+5]; int DFS(int x,int y) { LL r=0; if(x==17) { int m=0; for(int i=0;i<17;i++) if(field[i][y+1]=='#') m+=(1<<i); r=rec(y+1,m); } else if(field[x][y]=='#') r=DFS(x+1,y); else { if(x<16 && field[x+1][y]=='.') { field[x][y]=field[x+1][y]='#'; r=(r+DFS(x+1,y))%2000000011;; field[x][y]=field[x+1][y]='.'; } if(y<16 && field[x][y+1]=='.') { field[x][y]=field[x][y+1]='#'; r=(r+DFS(x+1,y))%2000000011;; field[x][y]=field[x][y+1]='.'; } if(x<16 && y<16 && field[x+1][y+1]=='.') { field[x][y]=field[x+1][y+1]='#'; r=(r+DFS(x+1,y))%2000000011;; field[x][y]=field[x+1][y+1]='.'; } } return (int)r%2000000011; } int rec(int y,int mask) { int &r=cache[y][mask]; if(r!=-1) ; else if(y==17) r=1; else r=DFS(0,y); return r; } int countArrangements(vector <int> X, vector <int> Y, int _N) { N=_N; for(int x=0;x<17;x++) for(int y=0;y<17;y++) field[x][y]='#'; for(int x=-N+1;x<=N-1;x++) { int b=(x<=0)?-N+1:-N+1+x; int c=(x<=0)?N-1+x:N-1; for(int y=b;y<=c;y++) field[x+offset][y+offset]='.'; } for(int i=0;i<X.size();i++) field[X[i]+offset][Y[i]+offset]='#'; int m=0; for(int i=0;i<17;i++) if(field[0][i]=='#') m+=(1<<i); memset(cache,-1,sizeof(cache)); return rec(0,m); } };