POJ 2441: Arrange the Bulls

概要

牡牛がN頭いて，M個のコートに1頭ずつ割り当てたい．
牡牛はそれぞれ好むコートが決まっている．
割り当て方は何通りあるか．

解法

bitDPやるだけ．
ただし，愚直に実装するとMLEを起こすはずなので，配列の再利用をする．

int N, M;
int P[30];
int B[30][30];
int dp[2][1 << 20];
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d", P+i);
        for(int j=0;j<P[i];++j){
            scanf("%d", B[i]+j);
            --B[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    int *prev = dp[0], *next = dp[1];
    prev[0] = 1;
    for(int i = 0; i < N; ++i){
        memset(next, 0, sizeof(dp[0]));
        for(int s = 0; s < (1 << M); ++s){
            if(!prev[s]) continue;
            for(int j = 0; j < P[i]; ++j){
                int f = 1 << B[i][j];
                if(!(f & s)){
                    next[s | f] += prev[s];
                }
            }
        }
        swap(prev, next);
    }
    int res = 0;
    for(int i = 0; i < (1 << M); ++i){
        res += prev[i];
    }
    printf("%d\n", res);
    return 0;
}