423 Assignments

ritsuko.c

//http://www.spoj.com/problems/ASSIGN/
#include <stdio.h>
#include <stdlib.h>

#define MAXN (1 << 22)

int n;
int asuka[22];
long long int memo[MAXN];

long long int dp(int mask) {
    if(memo[mask] != -1) return memo[mask];
    int i; int idx = 0; long long int gendou = 0;
    for(i = 0; i < 30; i++) if(mask & (1 << i)) idx += 1;
    if(idx == 0 && mask != 0) return 0;
    if(idx == n && mask == ((1 << n) - 1)) return memo[mask] = 1;
    if(idx == n && mask != ((1 << n) - 1)) return memo[mask] = 0;
    for(i = 0; i < n; i++) {
        if((!(mask & (1 << i))) && (asuka[idx] & (1 << i)))
            gendou += dp(mask | (1 << i));
    }
    return memo[mask] = gendou;
}

int main() {
    int c, temp, mask;
    int i, j;

    scanf("%d", &c);

    while(c--) {
        scanf("%d", &n);
        for(i = 0; i < (1 << (n+1)); i++)
                memo[i] = -1;
        for(i = 0; i < n; i++) {
            mask = 0;
            for(j = 0; j < n; j++) {
                scanf("%d", &temp);
                if(temp == 1) mask |= (1 << j);
            } asuka[i] = mask;
        }
        printf("%lld\n",dp(0));
    }

    return 0;
}