이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |