답안 #990675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990675	2024-05-31T01:27:41 Z	ToniB	Intergalactic ship (IZhO19_xorsum)	C++17	컴파일 오류	0 ms	0 KB

xorsum

#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() {	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];		}	}	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); ++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;
}

Compilation message

xorsum.cpp:1:31: warning: extra tokens at end of #include directive
    1 | #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() { 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];  } } 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); ++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];
      |                               ^~~~~~~~~
xorsum.cpp:1:10: fatal error: bits/stdc++.h>usin: No such file or directory
    1 | #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() { 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];  } } 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); ++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];
      |          ^~~~~~~~~~~~~~~~~~~~
compilation terminated.