Submission #1754506

---

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (long long i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;

int fld[26];
const int MOD=1e9+7;
vector<int> v;
ll dp[1<<25];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	REP(i,26) fld[i]=-1;

	REP(i,25) {
		int x; cin>>x;
		if(x==0) v.pb(i);
		else fld[x]=i;
	}
	dp[0]=1;
	REP(i,(1<<25)-1) {
		if(dp[i]) {
			int s=__builtin_popcount(i)+1;
			if(fld[s]>=0) {
				int r=fld[s];
				int x=r%5,y=r/5;
				if(((i>>r)&1)==0) {
					if(x>0&&x<4&&((i>>(r-1))^(i>>(r+1)))&1) continue;
					if(y>0&&y<4&&((i>>(r-5))^(i>>(r+5)))&1) continue;
					(dp[i|(1<<r)]+=dp[i])%=MOD;
				}
			}
			else {
				REP(j,v.size()) {
					int n=v[j];
					int x=n%5,y=n/5;
					if(((i>>n)&1)==0) {
						if(x>0&&x<4&&((i>>(n-1))^(i>>(n+1)))&1) continue;
						if(y>0&&y<4&&((i>>(n-5))^(i>>(n+5)))&1) continue;
						(dp[i|(1<<n)]+=dp[i])%=MOD;
					}
				}
			}
		}
	}
	cout<<dp[(1<<25)-1]<<endl;

	return 0;
}

Submission Info

Judge Result