2018第9回ブルーブリッジカップB組決勝問題第2題レーザー様式

タイトル:レーザー様式x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一字に並べて、宇宙に光の柱を打ち出します.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.明らかに、3台の機械しかなければ、全部で5つのスタイルになることができます.つまり、すべて閉めて(sorry、この時は声がなくて、これも1つです)1台を開けて、3種類で2台を開けて、1種類30台だけではよくありません.王はあなたに手伝ってもらうしかありません.30台のレーザで形成できるパターン種数を表す整数を提出する必要がある.
考え方:dfsでいい
コード:

#include
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const double esp = 1e-12;
const int ff = 0x3f3f3f3f;
map::iterator it;

ll ans;
int sta[52];
void dfs(int x)
{
	if(x == 31)
	{
		ans++;
		return ;
	}
	dfs(x+1);
	if(sta[x-1] == 0)
	{
		sta[x] = 1;
		dfs(x+1);
		sta[x] = 0;
	}
	return ;
}

int main()
{
	dfs(1);
	
	cout<