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);
		}
};