Участник:Kachanov vv/ASSIGN

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ASSIGN/

#include <iostream>
 
using namespace std;
 
const int max_value = 20;
const long max_comb = 1 << max_value;
 
int main() {
    int C, N, N_comb;
    int field[max_value][max_value];
    long long result[max_value][max_comb];
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N;
        N_comb = 1 << N;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N_comb; j++) {
                result[i][j] = 0;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> field[i][j];
            }
        }
        for (int i = 0; i < N; i++) {
            if (field[0][i]) {
                result[0][1 << i] = 1;
            }
        }
 
        for (int i = 1; i < N; i++) {
            for (int k = 0; k < N; k++) {
                if (!field[i][k]) {
                    continue;
                }
                for (int j = 0; j < N_comb; j++) {
                    if ((j >> k) & 1) {
                        result[i][j] += result[i - 1][j ^ (1 << k)];
                    }
                }
            }
        }
        long answer = 0;
        for (int i = 0; i < N_comb; i++) {
            answer += result[N - 1][i];
        }
        cout << answer << endl;
    }
 
    return 0;
}