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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20161
Problem 161 「トリオミノ」 †
トリオミノで9*12のマス目を埋め尽くす場合何通りの埋め尽くし方があるか。
ビット演算で楽して記述します。
計算時間一秒。

#include<stdio.h>
#include<map>
#include<iostream>
std::map<int,__int64> memo;
 
int main(){
	int check=(1+2+4)+(8+16+32)+(64+128+256);
	int ls[6]={1+(3<<9),1+(3<<8),3+(1<<9),3+(1<<10),1+(1<<9)+(1<<18),7};
	
	memo[0]=1;
 	std::map<int,__int64>::iterator it;
	for(int y=0;y<12;y++){
		
		for(int x=0;x<9;x++){
			std::map<int,__int64> next;
			for(it=memo.begin();it!=memo.end();it++){
				int perm=(*it).first;
				if(((perm>>x)&1)==1){
					next[perm]+=(*it).second;
					continue;
				}
				for(int i=0;i<6;i++){
					if((i==5)&&(x>6))continue;
					if(((i!=5)&&(i!=4)&&(i!=1))&&(x>7))continue;
					if((i==1)&&(x<1))continue;
					if((i==4)&&(y>9))continue;
					if((i!=4)&&(i!=5)&&(y>10))continue;
					int l=ls[i]<<x;
					if((perm&l)==0){
						next[(perm|l)]+=(*it).second;
					}
				}
			}
			memo.clear();
			memo.insert(next.begin(),next.end());
		}
		std::map<int,__int64> next;
		for(it=memo.begin();it!=memo.end();it++){
			int p=(*it).first;
			if((p&check)==check){
				next[p>>9]=(*it).second;
			}
		}
		memo.clear();
		memo.insert(next.begin(),next.end());
	}
	std::cout<<memo[0]<<"\n";
}