B. 말고스팟

한글 문제임에도 불구하고 문제를 이해하기가 다소 까다로운 편이다. 이 문제는 DP로 해결할 수 있다.

가능한 상황은 $2^N \times 2^M$ 가지가 있다. 이는 최대 $2^{40}$ 가지로 경우의 수가 꽤 많다. 가능한 경우를 줄이도록 생각해야한다. 현재 상황에서 문제별로 채점이 되었는지, 아직 채점이 되지 않았는지 경우는 총 $2^M$가지가 있다. 그 중 한 상황에서 여태까지 살아남은 사람은 필요충분으로 여태까지 채점된 문제들에 대해서 모두 Yes라고 대답한 사람이다. 따라서, 어떤 문제들을 채점했는지를 알면, 살아남은 사람 또한 알 수 있게 된다. 따라서, DP를 $2^M$ 가지 경우에 대해서 돌리면 된다.

#include <stdio.h> #include <vector> using namespace std; const int MOD = 1e9+9; int T,N,M,D[1<<20]; bool w[20][20]; int main() { int i,j,k; for (scanf("%d",&T);T--;){ scanf("%d%d",&N,&M); for (i=0;i<N;i++) for (j=0;j<M;j++) w[i][j] = 0; for (i=0;i<M;i++){ for (scanf("%d",&j);j--;){ scanf("%d",&k); --k; w[k][i] = 1; } } for (i=0;i<(1<<M);i++) D[i] = 0; D[0] = 1; for (int msk=0;msk<(1<<M);msk++) if (D[msk]){ vector <int> chk(N,1); for (i=0;i<M;i++) if (msk&(1<<i)){ for (j=0;j<N;j++) if (w[j][i]){ chk[j] = 0; } } for (i=0;i<N;i++) if (chk[i]) break; if (i == N) continue; for (i=0;i<M;i++) if (!(msk&(1<<i))){ int all=0,yes=0,first=0; for (j=N;j--;) if (chk[j]){ all++; if (!w[j][i]) yes++; first = w[j][i]; } bool ans_yes = (yes+yes>all || yes+yes == all && !first); if (!ans_yes) continue; D[msk^(1<<i)] = (D[msk^(1<<i)]+D[msk])%MOD; } } printf("%d\n",D[(1<<M)-1]); } }