QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352196#8335. Fast Hash TransformkarunaTL 1388ms13168kbC++202.3kb2024-03-12 23:09:272024-03-12 23:09:28

Judging History

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

  • [2024-03-12 23:09:28]
  • 评测
  • 测评结果:TL
  • 用时:1388ms
  • 内存:13168kb
  • [2024-03-12 23:09:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const int SZ = 65;
struct mat {
	bitset<SZ> a[SZ];
};
mat transpose(mat A) {
	mat B;
	for (int i = 0; i < SZ; i++) {
		for (int j = 0; j < SZ; j++) {
			B.a[i][j] = A.a[j][i];
		}
	}
	return B;
}
mat mult(mat A, mat B) {
	B = transpose(B);
	mat R;
	for (int i = 0; i < SZ; i++) {
		for (int j = 0; j < SZ; j++) {
			R.a[i][j] = (A.a[i] & B.a[j]).count() & 1;
		}
	}
	return R;
}
bitset<SZ> mult(mat A, bitset<SZ> x) {
	bitset<SZ> y;
	for (int i = 0; i < SZ; i++) {
		y[i] = (A.a[i] & x).count() & 1;
	}
	return y;
}

const int MAXN = 20202;
struct seg {
	mat tree[4 * MAXN];
	void update(int a, mat A, int l, int r, int x) {
		if (l == r) {
			tree[x] = A;
			return;
		}
		int m = (l + r) / 2;
		if (a <= m) {
			update(a, A, l, m, 2 * x);
		}
		else {
			update(a, A, m + 1, r, 2 * x + 1);
		}
		tree[x] = mult(tree[2 * x + 1], tree[2 * x]);
	}
	void query(int a, int b, bitset<SZ> &v, int l, int r, int x) {
		if (b < l || a > r) return;
		if (a <= l && r <= b) {
			v = mult(tree[x], v);
			return;
		}
		int m = (l + r) / 2;
		query(a, b, v, l, m, 2 * x);
		query(a, b, v, m + 1, r, 2 * x + 1);
	}
} t1;

mat f() {
	int m; cin >> m;
	mat A;
	A.a[SZ - 1][SZ - 1] = 1;
	for (int j = 0; j < m; j++) {
		ull s, o, a;
		cin >> s >> o >> a;
		for (int k = 0; k < SZ - 1; k++) {
			int b = (a >> k & 1);
			if (o == 0 && b == 1) {
				A.a[k][SZ - 1].flip();
			}
			else if (o == b) {
				A.a[k][(k + SZ - 1 - s) % (SZ - 1)].flip();
			}
		}
	}
	ull b; cin >> b;
	for (int k = 0; k < SZ - 1; k++) {
		if (b >> k & 1) {
			A.a[k][SZ - 1].flip();
		}
	}
	return A;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int n, q, c;
	cin >> n >> q >> c;
	for (int i = 0; i < n; i++) {
		t1.update(i, f(), 0, n - 1, 1);
	}
	while (q--) {
		int op; cin >> op;
		if (op == 0) {
			int s, e; ull x;
			cin >> s >> e >> x;
			bitset<SZ> v;
			for (int i = 0; i < SZ - 1; i++) {
				v[i] = (x >> i & 1);
			}
			v[SZ - 1] = 1;
			t1.query(s - 1, e - 1, v, 0, n - 1, 1);
			ull ans = 0;
			for (int i = 0; i < SZ - 1; i++) {
				ans ^= (ull)v[i] << i;
			}
			cout << ans << '\n';
		}
		else {
			int x; cin >> x;
			t1.update(x - 1, f(), 0, n - 1, 1);
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3676kb

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:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

9 9 3
32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...

output:

9487331362121050549
3906661590723083106
15757672015979182109
4975471776251039345
11503109206538591140
3763610618439604410

result:

ok 6 tokens

Test #3:

score: 0
Accepted
time: 18ms
memory: 3644kb

input:

1 20000 400
32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...

output:

11827781865759498816
7454610526276185721
9581050724293785387
2177163806257271094
14004004964877510141
18073834598135159471
16966489063087641088
12289032565388413023
17823140805867698239
18104549908461644670
15570008264282957124
12400954982104000299
9842549278742638708
16535034933613060362
1561642006...

result:

ok 19600 tokens

Test #4:

score: 0
Accepted
time: 324ms
memory: 4744kb

input:

500 20000 400
32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...

output:

9119093329811149961
16901643057538871933
17161855998497876349
3964234071281411558
13588188063229334268
15557968976322375381
4612345875926431452
9507168112801039022
9504318642653891468
217407202160767706
12982350345598971306
17957502630817476223
6353877977318728572
15552768639781831485
16778108770682...

result:

ok 19600 tokens

Test #5:

score: 0
Accepted
time: 1388ms
memory: 13168kb

input:

4000 20000 400
35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...

output:

11875257514484243925
3443357416933857062
16160011677622853538
1582145987019406393
15019762274690743371
3128972641411454448
10632018957963074870
2420532366876270818
16130728863118353230
15834956073901517645
18404809296474853851
10982435108266120760
16463778300806795274
11990886156320593058
1145171640...

result:

ok 19600 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

20000 20000 0
34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...

output:


result: