Submission #1872787

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
//#define INF 1100000000000000000LL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
//↓整数をpopcount orderで生成するセット
int next_perm(int v){
	//
	if(v==0)
		return (1<<30)-1;
	//v=0を入れると0除算が発生して停止するので注意！！
	int t=(v|(v-1))+1;
	int w=t|((((t&(-t))/(v&(-v)))>>1)-1);
	return w;
}
int element_0(int c){
	return (1<<c)-1;
}
//↑整数をpopcount orderで生成するセット
vint tate[26],yoko[26];
bool hantei(int v,int i){
	char a=0,b=0;
	//たての判定
	if(tate[i].size()==2)
		for(int j:tate[i]){
			if(v&(1<<j))
				a++;
		}
	//よこの判定
	if(yoko[i].size()==2)
		for(int j:yoko[i]){
			if(v&(1<<j))
				b++;
		}
	if(a==1 || b==1)
		return 0;
	else
		return 1;
}
int main() {
	//00~24の25マスについて
	int a[2]={-5,5};
	int b[2]={-1,1};
	//縦につながっているマスどうしのpathを記録
	for(int i=0;i<25;i++){
		for(int j=0;j<2;j++){
			if(i+a[j]<0 || 24<i+a[j])
				continue;
			tate[i].pb(i+a[j]);
		}
	}
	//横につながっているマスどうしのpathを記録
	for(int i=0;i<25;i++){
		for(int j=0;j<2;j++){
			if(j==0 && i%5==0)
				continue;
			if(j==1 && i%5==4)
				continue;
			yoko[i].pb(i+b[j]);
		}
	}
	
	//場所が決まっている数字
	//must[数字]=場所
	int must[26]={};
	for(int i=0;i<25;i++){
		must[i]=-1;
	}
	for(int i=0;i<25;i++){
		int c;
		cin>>c;
		if(c==0)
			continue;
		must[c-1]=i;
	}
	//DPテーブル
	int DP[1<<25]={};
	DP[0]=1;
	//popcount orderでDPテーブルをまわす
	for(int i=0;i<25;i++){
		//popしているbitの数がiである整数をまわす
		int v=element_0(i);
		while(1){
			//DP[v]==0のとき、そもそも無意味なので飛ばしてよい
			if(DP[v]==0){
				v=next_perm(v);
				if(v&(1<<25))
					break;
				continue;
			}
			//iを置く場所が決まっているとき、そこにおけるかどうかだけ見る
			if(must[i]!=-1){
				if((v&(1<<must[i]))==0 && hantei(v,must[i])){
					DP[v|(1<<must[i])]+=DP[v];
					DP[v|(1<<must[i])]%=MOD;
				}
			}
			//決まってないとき、全部見る
			else{
				for(int j=0;j<25;j++){
					if(v&(1<<j))
						continue;
					if(hantei(v,j)){
						DP[v|(1<<j)]+=DP[v];
						DP[v|(1<<j)]%=MOD;
					}
					//cout<<DP[v|(1<<j)]<<endl;
				}
			}
			v=next_perm(v);
			//25bit目が立っている数が現れたら止める
			if(v&(1<<25))
				break;
		}
	}
	cout<<DP[(1<<25)-1]<<endl;
    return 0;
}

Submission Info

Judge Result