제출 #443184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443184		fhvirus	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	617 ms	5952 KiB

xorsum

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif

const int kN = 1001;
const int kQ = 100001;
const int kL = 7;
const int MOD = 1e9 + 7;

int n, q;
vector<int> a, po2;
vector<tuple<int, int, int>> qs;
vector<vector<int>> cov1d, cov2d;

void build(int i, int j){
	int m = (1<<i) | (1<<j);
	for(int i = 1; i <= n; ++i) fill(AI(cov2d[i]), 0);
	for(auto [l, r, x]: qs) if((m & x) == m) ++cov2d[l][r];
	for(int l = 1; l <= n; ++l){
		for(int r = n; r >= l; --r) cov2d[l][r] += cov2d[l][r+1];
		for(int r = n; r >= l; --r) cov2d[l][r] += cov2d[l-1][r];
	}
}

int solve(int b1, int b2){
	int m1 = 1<<b1, m2 = 1<<b2, m = m1 | m2;
	vector<int> &covl = cov1d[b1], &covr = cov1d[b2];

	ll ans = 0;
	for(int l = 1; l <= n; ++l)
		for(int r = l; r <= n; ++r){
			int bo = cov2d[l][r];
			int ql = covl[l] - bo;
			int qr = covr[r] - bo;
			int no = q - bo - ql - qr;

			ll l0 = (ql == 0 ? 1 : po2[ql - 1]), l1 = po2[ql] - l0;
			ll r0 = (qr == 0 ? 1 : po2[qr - 1]), r1 = po2[qr] - r0;
			ll b0 = (bo == 0 ? 1 : po2[bo - 1]), b1 = po2[bo] - b0;
			if(a[l] & m1) swap(l0, l1);
			if(a[r] & m2) swap(r0, r1);

			ll tmp = 0;
			tmp += l1 * r1 % MOD * b0;
			tmp += l0 * r0 % MOD * b1;
			tmp = tmp % MOD * po2[no] * (l != r ? 2 : 1) % MOD;
			ans += tmp * l * (n - r + 1) % MOD;
		}
	ans = ans * m1 * m2 % MOD;
	return ans;
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	a.assign(n + 1, 0);
	cov1d.assign(kL, vector<int>(n + 2, 0));
	cov2d.assign(n + 1, vector<int>(n + 2, 0));
	for(int i = 1; i <= n; ++i) cin >> a[i];
	
	cin >> q;
	for(int l, r, x, i = 1; i <= q; ++i){
		cin >> l >> r >> x;
		qs.pb(l, r, x);
		for(int j = 0; j < kL; ++j)
			if(x >> j & 1) ++cov1d[j][l], --cov1d[j][r+1];
	}

	po2.assign(q + 1, 1);
	for(int i = 1; i <= q; ++i){
		po2[i] *= po2[i-1] * 2;
		po2[i] -= po2[i] >= MOD ? MOD : 0;
	}

	for(int j = 0; j < kL; ++j){
		for(int i = 1; i <= n; ++i)
			cov1d[j][i] += cov1d[j][i-1];
	}

	ll ans = 0;
	for(int i = 0; i < kL; ++i)
		for(int j = i; j < kL; ++j){
			build(i, j);
			ans += solve(i, j);
			if(i != j) ans += solve(j, i);
		}

	ans %= MOD;
	cout << ans << '\n';
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp: In function 'int solve(int, int)':
xorsum.cpp:44:30: warning: unused variable 'm' [-Wunused-variable]
   44 |  int m1 = 1<<b1, m2 = 1<<b2, m = m1 | m2;
      |                              ^

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8