记录编号	601434	评测结果	AAAAAAAAAA
题目名称	3118.[GXOI/GZOI2019]与或和	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	8.061 s
提交时间	2025-06-20 19:55:13	内存使用	108.84 MiB

#include <cstdio>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
typedef long long ll;

template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-')
      f = -1;
  for (; isdigit(ch); ch = getchar())
    res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0)
    x = -x, putchar('-');
  static int sta[sizeof(T) * 4], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAXN = 1010;
const ll MOD = 1e9 + 7;

int n;
int a[MAXN][MAXN];
bool onedigit[MAXN][MAXN][32];
int s[MAXN][MAXN][32][2];
int sta[MAXN];

ll work(int b) {
  ll res = 0;
  for (int k = 0; k < 31; ++k) {
    for (int i = 1; i <= n; ++i) {
      ll ans = 0, top = 0;
      for (int j = 1; j <= n; ++j) {
        ans += s[i][j][k][b];
        while (top && s[i][sta[top]][k][b] >= s[i][j][k][b]) {
          ans -= (sta[top] - sta[top - 1]) * (s[i][sta[top]][k][b] - s[i][j][k][b]);
          top--;
        }
        res += (b ? ans : i * j - ans) << k;
        res %= MOD;
        sta[++top] = j;
      }
    }
  }
  return res;
}

int main() {
  freopen("andorsum.in", "r", stdin);
  freopen("andorsum.out", "w", stdout);
  n = read<int>();
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      a[i][j] = read<int>();
      for (int k = 0; k < 31; ++k) {
        if ((a[i][j] >> k) & 1) {
          s[i][j][k][1] = s[i - 1][j][k][1] + 1;
          s[i][j][k][0] = 0;
        } else {
          s[i][j][k][0] = s[i - 1][j][k][0] + 1;
          s[i][j][k][1] = 0;
        }
      }
    }
  }
  write(work(1), ' ');
  write(work(0));
  return 0;
}