Submission #1291196

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <vector>

using namespace std;
#define MOD 1000000007

bool B[26];
int T[1 << 25];
int mp[26];

int bit_count(int i) {
    i = (i & 0x55555555) + (i >> 1 & 0x55555555);
    i = (i & 0x33333333) + (i >> 2 & 0x33333333);
    i = (i & 0x0f0f0f0f) + (i >> 4 & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + (i >> 8 & 0x00ff00ff);
    return (i & 0x0000ffff) + (i >> 16 & 0x0000ffff);
}

bool has_i(int state, int i) {
    int pos = 1 << i;
    return (state & pos) > 0;
}

int minus_i(int state, int i) {
    int pos = 1 << i;
    return state - pos;
}

int dfs_count(int state) {
    if (T[state] != -1)
        return T[state];
    int c = bit_count(state);
    if (B[c]) {
        int j = mp[c];
        if (!has_i(state, j)) {
            T[state] = 0;
            return 0;
        }
        int x = j % 5;
        int y = j / 5;
        if (0 < x && x < 4 && (has_i(state, j + 1) ^ (has_i(state, j - 1)))) {
            T[state] = 0;
            return 0;
        }
        if (0 < y && y < 4 && (has_i(state, j + 5) ^ (has_i(state, j - 5)))) {
            T[state] = 0;
            return 0;
        }
        int res = dfs_count(minus_i(state, j));
        T[state] = res;
        return res;
    } else {
        int sum = 0;
        for (int j = 0; j < 25; j++) {
            if (!has_i(state, j)) {
                continue;
            }
            int x = j % 5;
            int y = j / 5;
            if (0 < x && x < 4 &&
                (has_i(state, j + 1) ^ (has_i(state, j - 1)))) {
                continue;
            }
            if (0 < y && y < 4 &&
                (has_i(state, j + 5) ^ (has_i(state, j - 5)))) {
                continue;
            }
            sum += dfs_count(minus_i(state, j));
            sum %= MOD;
        }
        T[state] = sum;
        return sum;
    }
}

int main() {
    for (int i = 0; i < (1 << 25); i++) {
        T[i] = -1;
    }
    for (int i = 0; i < 25; i++) {
        int c;
        cin >> c;
        if (c != 0) {
            B[c] = true;
            mp[c] = i;
        }
    }
    T[0] = 1;
    cout << dfs_count((1 << 25) - 1) << endl;
    return 0;
}

Submission Info

Judge Result