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

Posted by xiaodao
Category: 日常