比赛 |
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;
}