Submission #11447703

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

template <int MOD = 1000000007>
struct Mint {
    int x;

    Mint() : x(0) {}
    Mint(long long t) {
        x = t % MOD;
        if (x < 0) x += MOD;
    }

    Mint pow(int n) {
        Mint res(1), t(x);
        while (n > 0) {
            if (n & 1) res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }

    Mint inv() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Mint(u);
    }

    Mint &operator+=(Mint a) {
        x += a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Mint &operator-=(Mint a) {
        x += MOD - a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Mint &operator*=(Mint a) {
        x = int(1LL * x * a.x % MOD);
        return *this;
    }

    Mint &operator/=(Mint a) {
        return (*this) *= a.inv();
    }

    Mint operator+(Mint a) const {
        return Mint(x) += a;
    }
    Mint operator-(Mint a) const {
        return Mint(x) -= a;
    }
    Mint operator*(Mint a) const {
        return Mint(x) *= a;
    }
    Mint operator/(Mint a) const {
        return Mint(x) /= a;
    }

    Mint operator-() const {
        return Mint(-x);
    }

    bool operator==(const Mint a) {
        return x == a.x;
    }
    bool operator!=(const Mint a) {
        return x != a.x;
    }
    bool operator<(const Mint a) {
        return x < a.x;
    }

    friend ostream &operator<<(ostream &os, const Mint &a) {
        return os << a.x;
    }

    friend istream &operator>>(istream &is, Mint &a) {
        int t;
        is >> t;
        a = Mint<MOD>(t);
        return (is);
    }
};

bool check(vector<vector<int>> &x) {
    rep(i, 3) {
        rep(j, 5) {
            if ((x[i][j] < x[i + 1][j] && x[i + 1][j] < x[i + 2][j]) ||
                (x[i][j] > x[i + 1][j] && x[i + 1][j] > x[i + 2][j]))
                return false;
        }
    }
    rep(i, 5) {
        rep(j, 3) {
            if ((x[i][j] < x[i][j + 1] && x[i][j + 1] < x[i][j + 2]) ||
                (x[i][j] > x[i][j + 1] && x[i][j + 1] > x[i][j + 2]))
                return false;
        }
    }
    return true;
}

signed main() {
    const int n = 5;
    bool use[n * n + 1] = {};
    vector<P> e;
    vector<vector<int>> x(n, vector<int>(n));
    rep(i, n) {
        rep(j, n) {
            cin >> x[i][j];
            if (x[i][j] == 0)
                e.emplace_back(i, j);
            else
                use[x[i][j]] = true;
        }
    }
    if (e.size() > 8) return 0;
    vector<int> v;
    for (int i = 1; i <= n * n; i++) {
        if (!use[i]) v.emplace_back(i);
    }
    sort(ALL(v));
    Mint<> ans = 0;
    do {
        rep(i, e.size()) {
            x[e[i].first][e[i].second] = v[i];
        }
        if (check(x)) ans += 1;
    } while (next_permutation(ALL(v)));
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result