Submission #1612078

---

Source Code Expand

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
//*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int A[25];
int fix[26];    //既に指定されている数字の場所fix[5]:5が入っている場所インデックス
int dp[1<<25];
vector<int> V;

signed main()
{
    REP(i,26) fix[i] = -1;
    REP(i,25) {
        cin >> A[i];
        if (A[i] == 0) V.push_back(i);
        else fix[A[i]] = i;
    }

    dp[0] = 1;
    //配るDP
    for (int mask=0; mask<(1<<25)-1; mask++) if (dp[mask]) {
        int b = __builtin_popcount(mask) + 1;   //次に置く数字
        if (fix[b] >= 0) {
            //次に置く数字bの場所が指定されていた場合
            int r = fix[b];
            int y = r / 5;
            int x = r % 5;
            if ((mask & (1 << r)) == 0) {
                //これから置く場合
                if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                dp[mask ^ (1 << r)] += dp[mask];
                if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
            }
        } else {
            for (int r : V) {
                int y = r / 5;
                int x = r % 5;
                if ((mask & (1 << r)) == 0) {
                    if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                    if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                    dp[mask ^ (1 << r)] += dp[mask];
                    if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
                }
            }
        }
    }

    cout << dp[(1<<25)-1] << endl;
}

Submission Info

Judge Result