【BZOJ】【P 2734】【HNOI 2012】【集合選択数】【状圧DP】【問題解】

転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=2734
こうぞうマトリクス
1 3 9
2 6
4
それぞれの数の左が彼の3倍、下が彼の2倍になるようにして、そこでこの問題はこの行列の中で隣接しない数を取るのに何種類の取り方があるかに変換して、互いにKingを侵さないのと似ています
PS:longlongのmodは本当に遅くて爆発して、intに変えてTLEがなくなりました
Code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef int  lld;
lld n,X,Y;
lld vis[200001];
lld mp[201][201];
lld canopt[1<<14];
lld ok[1010][1010];

	lld deb=0;
	
inline void Make_Matrix(lld s){
	memset(mp,0,sizeof(mp));
	mp[1][1]=s;
	X=1,Y=1;
	vis[s]=1;
	for(lld i=2,j=s*2;j<=n;i++,j*=2)
		mp[i][1]=j,X=i,vis[j]=1;
	for(lld i=2,j=s*3;j<=n;i++,j*=3)
		mp[1][i]=j,Y=i,vis[j]=1;
	for(lld i=2;i<=X;i++)
	for(lld j=2;j<=Y;j++){
		if(mp[i-1][j]*2<=n)
		mp[i][j]=mp[i-1][j]*2,vis[mp[i][j]]=1;
	}
	for(lld i=1;i<=X;i++)
	for(lld j=1;j<=Y;j++){
		if(mp[i][j]){
			mp[i][0]++;
			mp[0][j]++;
		}
	}
	if(deb)
	for(lld i=1;i<=X;i++){
		for(lld j=1;j<=Y;j++)
			cout<<mp[i][j]<<" ";
		cout<<endl;
	}//if(deb)cout<<endl;
}
inline bool ok1(lld x){
	if(x&(x<<1))return false;
	if(x&(x>>1))return false;
	return true;
} 
inline bool ok2(lld x,lld y){
	if(x&y)return false;
	return true;
}
lld f[44][3010];
inline lld DP(){
	memset(f,0,sizeof(f));
	f[0][1]=1;
	for(int i=0;i<X;i++){
		for(int j=1;j<=canopt[0];j++){
			if(canopt[j]>>mp[i][0] >0)break;
			for(int k=1;k<=canopt[0];k++){
				if(canopt[k]>>mp[i+1][0]>0)break;
				if(ok2(canopt[j],canopt[k])){
					f[i+1][k]+=f[i][j];
					f[i+1][k]%=1000000001;
				}
			}
		}
	}
	lld ans=0;
	for(int i=1;i<=canopt[0];i++)
	if(canopt[i]>>mp[X][0]>0)break;
	else ans+=f[X][i];
	return ans;
}
inline void Pre(){
	for(lld i=0;i<(1<<14);i++)
	if(ok1(i))
	canopt[++canopt[0]]=i;
	for(lld i=1;i<=canopt[0];i++){
		for(lld j=1;j<=canopt[0];j++)
		if(ok2(canopt[i],canopt[j]))
		ok[i][j]=ok[j][i]=1;
	}
}
int main(){
	cin>>n;
	Pre();
	long long ans=1;
	for(lld i=1;i<=n;i++){
		if(!vis[i]){
			Make_Matrix(i);
			ans*=DP();
			ans%=1000000001;
		}
	}
	cout<<ans<<endl;
	return 0;
}