QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#656177 | #8335. Fast Hash Transform | rizynvu | ML | 0ms | 0kb | C++14 | 2.9kb | 2024-10-19 11:41:46 | 2024-10-19 11:41:47 |
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