oj.uz

답안 #227525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227525 2020-04-27T16:37:00 Z srvlt Intergalactic ship (IZhO19_xorsum) C++14
83 / 100
 1000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int N = 1003, M = 100003, K = 128, MOD = 1e9 + 7;
int n, q, a[N], pw[M];
vector <pii> L[N], R[N];
 
int bit[K], mask[K];
 
struct basis {
	short int b[7];
	int sz = 0, bsz = 0;
	bitset <K> can;
	basis() {
		can[0] = 1;
	}
	void clear() {
		sz = 0;
		memset(& b, 0, sizeof(b));
		bsz = 0;
		can.reset();
		can[0] = 1;
	};
	void upd() {
		can.reset();
		for (int i = 0; i < (1 << bsz); i++) {
			if (i > 0) {
				mask[i] = mask[i ^ (1 << bit[i])] ^ b[bit[i]];
			}
			can[mask[i]] = 1;
		}
	};
	bool add(int x) {
		sz++;
		if (can[x]) {
			return false;
		}
		for (int i = 0; i < bsz; i++) {
			x = min(x, x ^ b[i]);
		}
		b[bsz++] = x;
		upd();
		return true;
	}
	int ways() {
		return pw[sz - bsz];
	}
};
 
basis cur, C[N][N], A[N][N];
short int f[K][N][N], g[K];
int last[N][N];
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	pw[0] = 1;
	for (int i = 1; i < M; i++) {
		pw[i] = pw[i - 1] * 2 % MOD;
	}
	
	for (int i = 1; i < K; i++) {
		for (int j = 6; j >= 0; j--) {
			if (i >> j & 1) {
				bit[i] = j;
				break;
			}
		}
	}
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		R[r].pb({l, x});
		L[l].pb({r, x});
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		for (int r = n; r >= l; r--) {
			for (auto i : R[r]) {
				if (i.F <= l) {
					cur.add(i.S);
				}
			}
			C[l][r] = cur;
		}
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		last[l][l] = l;
		for (int r = l; r <= n; r++) {
			if (last[l][r] == r) {
				A[l][r] = cur;
				for (int i = 0; i < K; i++) {
					for (int j = 0; j < K; j++) {
						f[i][l][r] += j * cur.can[j ^ i];
					}
				}
			}	else {
				last[l][r] = last[l][r - 1];
			}
			for (auto i : R[r]) {
				if (i.F <= l && cur.add(i.S)) {
					last[l][r + 1] = r + 1;
				}
			}
		}
	}
	int ans = 0;
	for (int r = n; r >= 1; r--) {
		cur.clear();
		for (int i = 0; i < K; i++) {
			g[i] = 0;
			for (int j = 0; j < K; j++) {
				g[i] += j * cur.can[j ^ i];
			}
		}
		for (int l = r; l >= 1; l--) {
			int res = 0, pos = last[l][r];
			for (int i = 0; i < K; i++) {
				res += (int)C[l][r].can[i] * f[i ^ a[l]][l][pos] * g[i ^ a[r]];
				if (res >= MOD) {
					res -= MOD;
				}
			}
			res = (ll)res * C[l][r].ways() % MOD;
			res = (ll)res * A[l][pos].ways() % MOD;
			res = (ll)res * cur.ways() % MOD;
			res = (ll)res * pw[q - C[l][r].sz - A[l][pos].sz - cur.sz] % MOD;
			if (l == r) {
				res = (ll)res * ((MOD + 1) / 2) % MOD;
			}
			int occ = l * (n - r + 1);
			ans += (ll)res * occ % MOD;
			if (ans >= MOD) {
				ans -= MOD;
			}
    		for (auto i : L[l]) {
    			if (i.F >= r && cur.add(i.S)) {
    				for (int k = 0; k < K; k++) {
    					g[k] = 0;
    					for (int j = 0; j < K; j++) {
    						g[k] += j * cur.can[j ^ k];
    					}
    				}
    			}
    		}
    	}
    }
    cout << 2 * ans % MOD;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 80760 KB Output is correct
2 Correct 45 ms 81528 KB Output is correct
3 Correct 48 ms 82808 KB Output is correct
4 Correct 46 ms 82808 KB Output is correct
5 Correct 46 ms 82680 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 80760 KB Output is correct
2 Correct 45 ms 81528 KB Output is correct
3 Correct 48 ms 82808 KB Output is correct
4 Correct 46 ms 82808 KB Output is correct
5 Correct 46 ms 82680 KB Output is correct
6 Correct 88 ms 105848 KB Output is correct
7 Correct 75 ms 105872 KB Output is correct
8 Correct 77 ms 105720 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 107896 KB Output is correct
2 Correct 102 ms 105976 KB Output is correct
3 Correct 86 ms 105848 KB Output is correct
4 Correct 76 ms 105720 KB Output is correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 202 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 87936 KB Output is correct
2 Correct 59 ms 87928 KB Output is correct
3 Correct 58 ms 87928 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 87936 KB Output is correct
2 Correct 59 ms 87928 KB Output is correct
3 Correct 58 ms 87928 KB Output is correct
4 Correct 58 ms 88056 KB Output is correct
5 Correct 58 ms 88056 KB Output is correct
6 Correct 58 ms 88060 KB Output is correct
7 Correct 67 ms 88056 KB Output is correct

Subtask #7
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 80760 KB Output is correct
2 Correct 45 ms 81528 KB Output is correct
3 Correct 48 ms 82808 KB Output is correct
4 Correct 46 ms 82808 KB Output is correct
5 Correct 46 ms 82680 KB Output is correct
6 Correct 88 ms 105848 KB Output is correct
7 Correct 75 ms 105872 KB Output is correct
8 Correct 77 ms 105720 KB Output is correct
9 Correct 57 ms 87936 KB Output is correct
10 Correct 59 ms 87928 KB Output is correct
11 Correct 58 ms 87928 KB Output is correct
12 Correct 102 ms 105848 KB Output is correct
13 Correct 101 ms 105848 KB Output is correct
14 Correct 90 ms 105852 KB Output is correct
15 Correct 107 ms 105848 KB Output is correct

Subtask #8
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 80760 KB Output is correct
2 Correct 45 ms 81528 KB Output is correct
3 Correct 48 ms 82808 KB Output is correct
4 Correct 46 ms 82808 KB Output is correct
5 Correct 46 ms 82680 KB Output is correct
6 Correct 88 ms 105848 KB Output is correct
7 Correct 75 ms 105872 KB Output is correct
8 Correct 77 ms 105720 KB Output is correct
9 Correct 57 ms 87936 KB Output is correct
10 Correct 59 ms 87928 KB Output is correct
11 Correct 58 ms 87928 KB Output is correct
12 Correct 58 ms 88056 KB Output is correct
13 Correct 58 ms 88056 KB Output is correct
14 Correct 58 ms 88060 KB Output is correct
15 Correct 67 ms 88056 KB Output is correct
16 Correct 102 ms 105848 KB Output is correct
17 Correct 101 ms 105848 KB Output is correct
18 Correct 90 ms 105852 KB Output is correct
19 Correct 107 ms 105848 KB Output is correct
20 Correct 950 ms 210424 KB Output is correct
21 Correct 621 ms 209912 KB Output is correct
22 Correct 1000 ms 210296 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 80760 KB Output is correct
2 Correct 45 ms 81528 KB Output is correct
3 Correct 48 ms 82808 KB Output is correct
4 Correct 46 ms 82808 KB Output is correct
5 Correct 46 ms 82680 KB Output is correct
6 Correct 88 ms 105848 KB Output is correct
7 Correct 75 ms 105872 KB Output is correct
8 Correct 77 ms 105720 KB Output is correct
9 Correct 122 ms 107896 KB Output is correct
10 Correct 102 ms 105976 KB Output is correct
11 Correct 86 ms 105848 KB Output is correct
12 Correct 76 ms 105720 KB Output is correct
13 Runtime error 202 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -