Submission #1369459

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
constexpr int mod = 1'000'000'007;


inline bool is_valid_core(int mask, int rc, int p, int delta){
    if (rc == 0 or rc == 4) return true;
    bool LT = mask & (1 << (p - delta));
    bool RB = mask & (1 << (p + delta));
    return not(LT xor RB);
}

inline bool is_valid(int mask, int p){
    return is_valid_core(mask, p % 5, p, 1) and is_valid_core(mask, p / 5, p, 5);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> pos(25, -1);  // pos[v] v番（0はじまり）がどの位置に配置済みであるか。未配置の場合は -1
    vector<int> unzip;        // unzip[z] bit mask の下からz桁目は、どの位置（0-24）に該当するか。座標の復元操作。
    for (int idx = 0; idx != 25; ++idx){
        int v;
        cin >> v;
        if (v > 0){
            pos[v - 1] = idx;
        }else{
            unzip.push_back(idx);
        }
    }
    vector<int> dp(1 << 25, 0);  // dp[mask] mask のbitの立っている位置に、0からdp[mask].popcount() - 1 までを配置するパターン数
    dp[0] = 1;
    vector<int> pool = {0};           // pool: v-1 番まで配置したときの、mask のパターン
    for (int v = 0; v != 25; ++v){    // v: これから配置しようとしている番号
        vector<int> new_pool;
        if (pos[v] != -1){
            for (auto mask : pool){
                if (is_valid(mask, pos[v])){
                    auto new_mask = mask | (1 << pos[v]);
                    new_pool.push_back(new_mask);
                    dp[new_mask] += dp[mask] - mod;
                    if (dp[new_mask] < 0) dp[new_mask] += mod;
                }
            }
        }else{
            for (auto mask : pool){
                for (auto p: unzip){
                    if (mask & (1 << p)) continue;
                    if (is_valid(mask, p)){
                        auto new_mask = mask | (1 << p);
                        if (dp[new_mask] == 0) new_pool.push_back(new_mask);
                        dp[new_mask] += dp[mask] - mod;
                        if (dp[new_mask] < 0) dp[new_mask] += mod;
                    }
                }
            }
        }
        swap(pool, new_pool);
    }
    cout << dp[(1 << 25) - 1] << endl;
    return 0;
}

Submission Info

Judge Result