Problem A. Harry and Magical Computer

dfs()。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=3135139

貪心。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=3135141

Problem B. Harry And Magic Box

給定一個 n*m 個矩陣，問其中有多少 0/1 方案是的每一行，每一列至少有一個 1。

暴力冗斥。

const int N = int(50) + 9; Int C[N][N], A[N][N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif REP(i, N){ C[i][0] = 1; REP_1(j, i) C[i][j] = C[i-1][j-1] + C[i-1][j]; } REP_1(i, N){ REP_1(j, N){ A[i][j] = pow(2, i*j) - 1; REP_1(ii, i) REP_1(jj, j) if (ii != i || jj != j){ A[i][j] -= A[ii][jj] * C[i][ii] * C[j][jj]; } } } int n, m; while (~scanf("%d%d", &n, &m)){ OT(int(A[n][m])); } }

正常向冗斥：

f(i) 表示：至少 i 行是空的方案數。

//}/* .................................................................................................................................. */ const int N = int(50) + 9; Int C[N][N]; int n, m; Int f(int i){ return pow(pow(Int(2), n-i)-1, m) * C[n][i]; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif REP(i, N){ C[i][0] = 1; REP_1(j, i) C[i][j] = C[i-1][j-1] + C[i-1][j]; } while (~scanf("%d%d", &n, &m)){ Int z = 0; REP(i, n+1){ if (i&1) z -= f(i); else z += f(i);; } OT(int(z)); } }

Problem C.

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=3135282

Problem D.

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=3135430