11228: 【原1228】Matrix Sum

题目

题目描述

author: lostleaf 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1228

Description

给定一个 n 阶方阵 A ，求其中有多少个子矩阵元素之和分别为奇数和偶数。子矩阵指从原矩阵中选出一些连续的行与列，由这些行与列交点上的元素组成的矩阵。（A 也是 A 的子矩阵）

Input Format

第一行一个数 n

接下来 n 行，每行 n 个数，第 i 行第 j 个数为 A(i, j)

Output Format

两个数，分别为元素和是奇数的子矩阵个数与元素和是偶数的子矩阵个数

Hint

结果需要用 long long 表示

Sample Input 1

2
443 718
613 296

Sample Output 1

4 5

Sample Input 2

3
802 516 936
906 150 155
39 221 557

Sample Output 2

16 20

Limits

对于40%的数据, n<=10
对于70%的数据, n<=100
对于100%的数据, n<=400

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 4e2 + 10;
int A[maxN][maxN], temp[maxN] = {0}, N, zero[maxN];
long long ans0 = 0, ans1 = 0;

void count();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int temp1;
            cin >> temp1;
            A[i][j] = temp1 % 2;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[j] = A[i][j];
        }
        count();
        for (int j = i + 1; j < N; j++) {
            for (int k = 0; k < N; k++) {
                temp[k] += A[j][k];
                temp[k] %= 2;
            }
            count();
        }
        for (int j = 0; j < N; j++) {
            temp[j] = 0;
        }
    }
    ans1 = N * (N + 1) / 2;
    ans1 *= ans1;
    ans1 -= ans0;

    cout << ans0 << ' ' << ans1 << '\n';

    return 0;
}

void count() {
    int t = 0, len = 0;
    for (int i = 0; i < N; i++) {
        t++;
        if (temp[i] == 1) {
            zero[len++] = t;
            t = 0;
        }
    }

    if (len == 0) {
        return;
    } else {
        zero[len++] = ++t;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j += 2) {
                ans0 += (zero[i] * zero[j]);
            }
        }
        len = 0;
    }
}

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 405
using namespace std;
int a[MAX_N][MAX_N];
int sum[MAX_N];
int N;
long long ans_odd;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') ch = getchar();
    while (ch >= '0' && ch <= '9') res = ch - '0', ch = getchar();
    return res & 1;
}
void count_odd() {
    int cur = 0;
    int zeros[MAX_N]; zeros[0] = 0;
    register int i, j;
    for (i = 0; i < N; ++i) {
        ++cur;
        if (sum[i]) {
            zeros[++zeros[0]] = cur;
            cur = 0;
        }
    }
    if (!zeros[0]) return;
    zeros[++zeros[0]] = ++cur;
    for (i = 1; i < zeros[0]; ++i)
        for (j = i + 1; j <= zeros[0]; j += 2)
            ans_odd += zeros[i] * zeros[j];
}
int main() {
    scanf("%d", &N);
    register int i, j, k;
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j)
            a[i][j] = read();
    // calc from i-th row to j-th row
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) sum[j] = a[i][j];
        count_odd();
        for (j = i + 1; j < N; ++j) {
            for (k = 0; k < N; ++k) sum[k] = (sum[k] + a[j][k]) & 1;
            count_odd();
        }
    }
    printf("%lld %lld", ans_odd, (long long)N * N * (N + 1) * (N + 1) / 4 - ans_odd);
    return 0;
}