제출 #869132

#제출 시각아이디문제언어결과실행 시간메모리
869132KiaRezIntergalactic ship (IZhO19_xorsum)C++17
100 / 100
1279 ms23116 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 1e5+23, lg = 17; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } ll n, q, a[N], pw[N], X[N], ans, L[N], R[N]; int dp[1005][1005][4]; vector<int> vec[N]; int get(int b1, int b2) { return b1*2+b2; } void update(int b1, int b2) { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=0; k<4; k++) dp[i][j][k]=0; for(int i=1; i<=q; i++) { dp[L[i]][R[i]][get((X[i]>>b1)%2, (X[i]>>b2)%2)] ++; } for(int sz=n-1; sz>=1; sz--) { for(int l,r=sz; r<=n; r++) { l = r-sz+1; for(int b=0; b<4; b++) { dp[l][r][b] += (dp[l][r+1][b] + dp[l-1][r][b] - dp[l-1][r+1][b]); } } } } int main () { ios_base::sync_with_stdio(false), cin.tie(0); pw[0]=1; for(int i=1; i<N; i++) pw[i] = MOD(pw[i-1] * 2); cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; } cin>>q; for(int i=1; i<=q; i++) { cin>>L[i]>>R[i]>>X[i]; } for(int bi=0; bi<7; bi++) { for(int bj=0; bj<7; bj++) { update(bi, bj); for(int i=1; i<=n; i++) { for(int j=n; j>=i; j--) { int num=dp[i][j][3]; int numi=dp[i][i][2]+dp[i][i][3]-num; int numj=dp[j][j][1]+dp[j][j][3]-num; ll comb = 0; if(numi > 0) { if(numj > 0) { comb = MOD(MOD(pw[numi-1]*pw[numj-1])*pw[num]); } else { if(num > 0) { comb = MOD(pw[num-1] * pw[numi-1]); } else { if((a[j]>>bj)%2==1) comb = pw[numi-1]; } } } else if(numj > 0) { if(num > 0) { comb = MOD(pw[num-1] * pw[numj-1]); } else { if((a[i]>>bi)%2==1) comb = pw[numj-1]; } } else { if((a[i]>>bi)%2 == (a[j]>>bj)%2) { if(num > 0) comb = pw[num-1]; else { if((a[i]>>bi)%2==1) comb=1; } } } ans = MOD(ans + MOD(comb*pw[q-num-numi-numj])*MOD(pw[bi+bj]*MOD(1ll*i*(n-j+1))) * (i==j ? 1ll : 2ll)); } } } } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...