概要
牡牛が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; }