Submission #4636094

---

Source Code Expand

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

const int MOD = 1e9 + 7;

array<int, 1 << 25> dp;

void f(int mask, int pos) {
    if ((mask >> pos) & 1) return;
    int x = pos % 5;
    int y = pos / 5;
    if (x > 0 && x < 4 && ((mask >> (pos - 1)) ^ (mask >> (pos + 1))) & 1) {
        return;
    }
    if (y > 0 && y < 4 && ((mask >> (pos - 5)) ^ (mask >> (pos + 5))) & 1) {
        return;
    }
    dp[mask + (1 << pos)] += dp[mask];
    dp[mask + (1 << pos)] %= MOD;
}

int main() {
    vector<int> not_arranged;
    map<int, int> arranged;
    for (size_t i = 0; i < 25; i++) {
        int x;
        cin >> x;
        if (x) {
            arranged[x] = i;
        } else {
            not_arranged.push_back(i);
        }
    }

    dp[0] = 1;
    for (size_t mask = 0; mask < (1 << 25) - 1; mask++) {
        if (!dp[mask]) continue;
        int n = __builtin_popcount(mask) + 1;
        if (arranged.find(n) != end(arranged)) {
            f(mask, arranged[n]);
        } else {
            for (auto&& x : not_arranged) f(mask, x);
        }
    }

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

Submission Info

Judge Result