QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656177#8335. Fast Hash TransformrizynvuML 0ms0kbC++142.9kb2024-10-19 11:41:462024-10-19 11:41:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 11:41:47]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-19 11:41:46]
  • 提交

answer

#include<bits/stdc++.h>
using ull = unsigned long long;
int n, q, C;
constexpr int N = 65, W = 64;
struct matrix {
   int a[N][N];
   inline matrix() {memset(a, 0, sizeof(a));}
   inline int *operator [] (const int &x) {return a[x];}
   inline const int *operator [] (const int &x) const {return a[x];}
   inline matrix operator * (const matrix &b) const {
      matrix c;
      for (int i = 0; i < N; i++)
         for (int k = 0; k < N; k++)
            for (int j = 0; j < N; j++)
               c[i][j] ^= a[i][k] & b[k][j];
      return c;
   }
};
struct vector {
   int a[N];
   inline vector() {memset(a, 0, sizeof(a));}
   inline int &operator [] (const int &x) {return a[x];}
   inline int operator [] (const int &x) const {return a[x];}
   inline vector operator * (const matrix &b) const {
      vector c;
      for (int k = 0; k < N; k++)
         for (int i = 0; i < N; i++)
            c[i] ^= a[k] & b[k][i];
      return c;
   }
};
inline matrix init_mat() {
   matrix a;
   int m; ull B;
   scanf("%d", &m);
   while (m--) {
      int w, op; ull x;
      scanf("%d%d%llu", &w, &op, &x);
      for (int i = 0; i < W; i++) {
         int j = (i + w) % W;
         if (op == 1 && (~ x >> j & 1ull)) continue;
         if (op == 0 && (x >> j & 1ull)) {a[W][j] ^= 1; continue;}
         a[i][j] ^= 1;
      }
   }
   scanf("%llu", &B);
   a[W][W] = 1;
   for (int i = 0; i < W; i++) a[W][i] ^= (int)(B >> i & 1ull);
   return a;
}
inline vector init_vec() {
   vector a;
   ull x; scanf("%llu", &x);
   for (int i = 0; i < W; i++) a[i] = (int)(x >> i & 1ull);
   a[W] = 1;
   return a;
}
const int maxn = 2e4 + 10;
matrix tr[maxn * 4];
inline void build(int k = 1, int l = 1, int r = n) {
   if (l == r)
      return tr[k] = init_mat(), void();
   int mid = l + r >> 1;
   build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
   tr[k] = tr[k << 1] * tr[k << 1 | 1];
}
inline void update(int x, int k = 1, int l = 1, int r = n) {
   if (l == r)
      return tr[k] = init_mat(), void();
   int mid = l + r >> 1;
   x <= mid ? update(x, k << 1, l, mid) : update(x, k << 1 | 1, mid + 1, r);
   tr[k] = tr[k << 1] * tr[k << 1 | 1];
}
inline void query(int x, int y, vector &ans, int k = 1, int l = 1, int r = n) {
   if (x <= l && r <= y)
      return ans = ans * tr[k], void();
   int mid = l + r >> 1;
   if (x <= mid) query(x, y, ans, k << 1, l, mid);
   if (y  > mid) query(x, y, ans, k << 1 | 1, mid + 1, r);
}
matrix a[maxn];
int main() {
   scanf("%d%d%d", &n, &q, &C);
   build();
   for (int o, l, r; q--; ) {
      scanf("%d%d", &o, &l);
      if (! o) {
         scanf("%d", &r);
         vector b = init_vec();
         query(l, r, b);
         ull x = 0;
         for (int i = 0; i < W; i++) x |= (ull)(b[i]) << i;
         printf("%llu\n", x);
      } else {
         update(l);
      }
   }
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

output:

64206
2023
31
1112

result: