Submission #1332759

#TimeUsernameProblemLanguageResultExecution timeMemory
1332759model_codePet (COCI26_pet)C++20
110 / 110
390 ms5948 KiB
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using i128 = __int128_t;

static string to_string_i128(i128 x) {
    if (x == 0) return "0";
    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }
    string s;
    while (x > 0) {
        int d = x % 10;
        s.push_back(char('0' + d));
        x /= 10;
    }
    if (neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> g(n);
    for (int i = 0; i < n; ++i) {
        cin >> g[i];
    }

    vector<int> R(n, 0), C(m, 0);
    int rowBlocks = (m + 63) >> 6;
    int colBlocks = (n + 63) >> 6;
    vector<vector<ull>> rowBits(n, vector<ull>(rowBlocks, 0));
    vector<vector<ull>> colBits(m, vector<ull>(colBlocks, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == '1') {
                ++R[i];
                ++C[j];
                rowBits[i][j >> 6] |= 1ULL << (j & 63);
                colBits[j][i >> 6] |= 1ULL << (i & 63);
            }
        }
    }

    vector<long long> rowWeighted(n, 0), colWeighted(m, 0);
    for (int i = 0; i < n; ++i) {
        long long sum = 0;
        for (int j = 0; j < m; ++j) if (g[i][j] == '1') {
            sum += (C[j] - 1LL);
        }
        rowWeighted[i] = sum;
    }

    for (int j = 0; j < m; ++j) {
        long long sum = 0;
        for (int i = 0; i < n; ++i) if (g[i][j] == '1') {
            sum += (R[i] - 1LL);
        }
        colWeighted[j] = sum;
    }

    vector<long long> rowSumByCol(m, 0);
    vector<long long> colSumByRow(n, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) if (g[i][j] == '1') {
            rowSumByCol[j] += rowWeighted[i];
            colSumByRow[i] += colWeighted[j];
        }
    }

    i128 unrestricted = 0;
    for (int i = 0; i < n; ++i) {
        long long rowPart = R[i] - 1LL;
        long long rowPart2 = rowPart * rowPart;
        for (int j = 0; j < m; ++j) if (g[i][j] == '1') {
            long long colPart = C[j] - 1LL;
            long long colPart2 = colPart * colPart;

            i128 rowFirst = (i128)rowPart * (rowSumByCol[j] - rowWeighted[i] - colPart2);
            i128 colFirst = (i128)colPart * (colSumByRow[i] - colWeighted[j] - rowPart2);

            unrestricted += rowFirst + colFirst;
        }
    }

    auto intersect_count = [](const vector<ull> &a, const vector<ull> &b) {
        int len = (int) a.size();
        int cnt = 0;
        for (int i = 0; i < len; ++i) {
            cnt += __builtin_popcountll(a[i] & b[i]);
        }
        return cnt;
    };

    i128 bad = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int t = intersect_count(rowBits[i], rowBits[j]);
            if (t >= 2) bad += 2LL * t * (t - 1);
            else if (t == 1) bad += 0;
        }
    }

    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            int t = intersect_count(colBits[i], colBits[j]);
            if (t >= 2) bad += 2LL * t * (t - 1);
            else if (t == 1) bad += 0;
        }
    }

    i128 ans = unrestricted - bad;
    cout << to_string_i128(ans) << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...