oj.uz

Submission #990686

# Submission time Handle Problem Language Result Execution time Memory
990686 2024-05-31T01:59:37 Z ToniB Intergalactic ship (IZhO19_xorsum) C++17
8 / 100
 1838 ms 139960 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 105;
const int K = 32;
const int Q = 1e5 + 5;

inline int add(int a, int b) {
	return (a + b >= MOD) ? a + b - MOD : a + b;
}
inline int mul(int a, int b) {
	return (long long) a * b % MOD;
}

int n, a[N], q, l[N], r[N], x[N], pre[N], ans;
int dp[N][N][N * K], pt[Q];
vector<int> queries[N];

void solveSimpleSegments() {
	assert(!(n <= 30 && q <= 20));
	pt[0] = 1;
	for (int i = 1; i <= q; ++i) pt[i] = mul(pt[i - 1], 2);
	for (int i = 0; i < q; ++i) {
		queries[l[i]].push_back(x[i]);
	}
	pre[0] = queries[0].size();
	for (int i = 1; i < n; ++i) pre[i] = queries[i].size() + pre[i - 1];

	for (int i = 0; i < n; ++i) {
		dp[i][i][a[i]] = 1;
		for (int val : queries[i]) {
			vector<int> tmp (K, 0);
			for (int j = 0; j < K; ++j) {
				tmp[j] = add(dp[i][i][j], dp[i][i][j ^ val]);
			}
			for (int j = 0; j < K; ++j) dp[i][i][j] = tmp[j];
		}
		int uk = 0;
		for (int j = 0; j < K; ++j) uk = add(uk, dp[i][i][j]);
		assert(uk == pt[queries[i].size()]);
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			for (int sum = 0; sum < n * K; ++sum) {
				for (int k = 0; k < min(K, sum + 1); ++k) {
					dp[i][j][sum] = add(dp[i][j][sum], mul(dp[i][j - 1][sum - k], dp[j][j][k]));
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int sum = 0; sum < n * K; ++sum) {
				int rem = q - (pre[j] - (i ? pre[i - 1] : 0));
				int val = mul(sum, sum);
				int count = mul(dp[i][j][sum], pt[rem]);
				ans = add(ans, mul(val, count));
			}
		}
	}
	cout << ans << "\n";
}

int main(){
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];

	cin >> q;
	int maxlen = 0;
	for (int i = 0; i < q; ++i) {
		cin >> l[i] >> r[i] >> x[i], --l[i], --r[i];
		maxlen = max(maxlen, r[i] - l[i]);
	}
	if (!maxlen) {
		solveSimpleSegments();
		return 0;
	}

	for (int i = 0; i < (1 << q); ++i) {
		for (int j = 0; j < q; ++j) {
			if (i & 1 << j) {
				pre[l[j]] ^= x[j];
				pre[r[j] + 1] ^= x[j];
			}
		}
		for (int i = 1; i < n; ++i) pre[i] ^= pre[i - 1];
		for (int i = 0; i < n; ++i) a[i] ^= pre[i];

		int sum = 0;
		for (int i = 0; i < n; ++i) {
			int cur = 0;
			for (int j = i; j < n; ++j) {
				cur += a[j];
				sum += cur * cur;
				sum %= MOD;
			}
		}
		ans += sum;
		ans %= MOD;

		for (int i = 0; i < n; ++i) {
			a[i] ^= pre[i];
			pre[i] = 0;
		}
	}

	cout << ans << "\n";

	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1623 ms 139960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1838 ms 348 KB Output is correct
2 Correct 1822 ms 420 KB Output is correct
3 Correct 1775 ms 344 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1838 ms 348 KB Output is correct
2 Correct 1822 ms 420 KB Output is correct
3 Correct 1775 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -