比赛 2025.6.7 评测结果 AAAAAAAAAA
题目名称 与或和 最终得分 100
用户昵称 健康铀 运行时间 5.984 s
代码语言 C++ 内存使用 6.99 MiB
提交时间 2025-06-07 11:50:27
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e9+7;

int main() {
	    freopen("andorsum.in", "r", stdin);
	    freopen("andorsum.out", "w", stdout);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    ll t = ((ll)n * (n + 1) / 2) % M;
    t = (t * t) % M;

    ll A = 0, O = 0;
    for (int k = 0; k < 32; k++) {
        vector<vector<int>> b(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                b[i][j] = (a[i][j] >> k) & 1;

        ll c1 = 0;
        vector<int> h(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (b[i][j] == 1)
                    h[j]++;
                else
                    h[j] = 0;
            }
            stack<int> s;
            vector<ll> d(n, 0);
            ll cur = 0;
            for (int j = 0; j < n; j++) {
                while (!s.empty() && h[s.top()] >= h[j])
                    s.pop();
                if (s.empty())
                    d[j] = (ll)h[j] * (j + 1);
                else
                    d[j] = d[s.top()] + (ll)h[j] * (j - s.top());
                s.push(j);
                cur = (cur + d[j]) % M;
            }
            c1 = (c1 + cur) % M;
        }

        ll c0 = 0;
        fill(h.begin(), h.end(), 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (b[i][j] == 0)
                    h[j]++;
                else
                    h[j] = 0;
            }
            stack<int> s;
            vector<ll> d(n, 0);
            ll cur = 0;
            for (int j = 0; j < n; j++) {
                while (!s.empty() && h[s.top()] >= h[j])
                    s.pop();
                if (s.empty())
                    d[j] = (ll)h[j] * (j + 1);
                else
                    d[j] = d[s.top()] + (ll)h[j] * (j - s.top());
                s.push(j);
                cur = (cur + d[j]) % M;
            }
            c0 = (c0 + cur) % M;
        }

        ll v = (1LL << k) % M;
        A = (A + v * c1) % M;
        ll oc = (t - c0 + M) % M;
        O = (O + v * oc) % M;
    }

    cout << A << " " << O << endl;
    return 0;
}