プロジェクトオイラー問215 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20215
Problem 215 「亀裂のない壁」 †
1*2と1*3のレンガを使って伝播亀裂のない32*10の壁を作る。
何通りの作りかたがあるか？

漸化式を探索するだけです。
計算時間１秒。

#include<stdio.h>
#include<map>
#include<iostream>

std::map<unsigned int,__int64> ms[11];


void f(int p,unsigned int d,unsigned int u,__int64 c,int r){
	if(p+2==32||p+3==32){
		ms[r][u]+=c;
	}else{
		if(p+2<=32){
			int p1=p+2;
			if(((d>>(p1-1))&1)==0){
				f(p1,d,u+(1<<(p1-1)),c,r);
			}
		}
		if(p+3<=32){
			int p1=p+3;
			if(((d>>(p1-1))&1)==0){
				f(p1,d,u+(1<<(p1-1)),c,r);
			}
		}
	}
}

int main(){
	ms[0][0]=1;
	std::map<unsigned int,__int64>::iterator it;
	for(int i=1;i<=10;i++){
 		for(it=ms[i-1].begin();it!=ms[i-1].end();it++){
			unsigned int d=(*it).first;
			__int64 c=(*it).second;
			f(0,d,0,c,i);
		}
	}
	__int64 ans=0;
	for(it=ms[10].begin();it!=ms[10].end();it++){
		ans+=(*it).second;
	}
	std::cout<<ans<<"\n";
}