// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=1e3+10;
const ll mod =1e9+7 ;
const ll base=1e13;
ll a[maxn];
ll l[maxn*maxn];
ll r[maxn*maxn];
ll x[maxn*maxn];
ll gt[maxn];
ll gtv[maxn];
ll mul(ll a,ll n)
{
if (n==0)
return 1;
if (n==1)
return a;
ll t=mul(a,n/2);
if (n%2==0)
return (t*t)%mod;
return ((t*t)%mod*a)%mod;
}
void setup()
{
gt[0]=1;
for (int i=1; i<maxn; i++)
{
gt[i]=(gt[i-1]*i)%mod;
}
gtv[maxn-1]=mul(gt[maxn-1],mod-2);
for (int i=maxn-2; i>=0; i--)
{
gtv[i]=(gtv[i+1]*(i+1))%mod;
}
}
ll nck(ll n,ll k)
{
if (n<k)
return 0;
return ((gt[n]*gtv[k])%mod*gtv[n-k])%mod;
}
vector<vector<ll>> dpl;
vector<vector<ll>> dpr;
vector<vector<ll>> dpb;
const int root = 3, MOD = (119<<23)+1; // 998244353
// For p < 2^30 there is also e.g. (5<<25, 3), (7<<26, 3)
/// (479<<21, 3) and (483<<21, 5). Last two are > 10^9.
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool ckmin(T& a, const T& b)
{
return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
return a < b ? a = b, 1 : 0;
}
int pct(int x)
{
return __builtin_popcount(x);
}
int bits(int x)
{
return 31-__builtin_clz(x); // floor(log2(x))
}
int cdiv(int a, int b)
{
return a/b+!(a<0||a%b == 0); // division of a by b rounded up, assumes b > 0
}
int fstTrue(function<bool(int)> f, int lo, int hi)
{
hi ++;
assert(lo <= hi); // assuming f is increasing
while (lo < hi) // find first index such that f is true
{
int mid = (lo+hi)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
template<class T> void remDup(vector<T>& v)
{
sort(all(v));
v.erase(unique(all(v)),end(v));
}
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x)
{
cin >> x;
}
void re(db& d)
{
str t;
re(t);
d = stod(t);
}
void re(ld& d)
{
str t;
re(t);
d = stold(t);
}
template<class H, class... T> void re(H& h, T&... t)
{
re(h);
re(t...);
}
template<class A> void re(complex<A>& c)
{
A a,b;
re(a,b);
c = {a,b};
}
template<class A, class B> void re(pair<A,B>& p)
{
re(p.f,p.s);
}
template<class A> void re(vector<A>& x)
{
trav(a,x) re(a);
}
template<class A, size_t SZ> void re(array<A,SZ>& x)
{
trav(a,x) re(a);
}
// TO_STRING
#define ts to_string
str ts(char c)
{
return str(1,c);
}
str ts(bool b)
{
return b ? "true" : "false";
}
str ts(const char* s)
{
return (str)s;
}
str ts(str s)
{
return s;
}
template<class A> str ts(complex<A> c)
{
stringstream ss;
ss << c;
return ss.str();
}
str ts(vector<bool> v)
{
str res = "{";
F0R(i,sz(v)) res += char('0'+v[i]);
res += "}";
return res;
}
template<size_t SZ> str ts(bitset<SZ> b)
{
str res = "";
F0R(i,SZ) res += char('0'+b[i]);
return res;
}
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) // containers with begin(), end()
{
bool fst = 1;
str res = "{";
for (const auto& x: v)
{
if (!fst)
res += ", ";
fst = 0;
res += ts(x);
}
res += "}";
return res;
}
template<class A, class B> str ts(pair<A,B> p)
{
return "("+ts(p.f)+", "+ts(p.s)+")";
}
// OUTPUT
template<class A> void pr(A x)
{
cout << ts(x);
}
template<class H, class... T> void pr(const H& h, const T&... t)
{
pr(h);
pr(t...);
}
void ps()
{
pr("\n"); // print w/ spaces
}
template<class H, class... T> void ps(const H& h, const T&... t)
{
pr(h);
if (sizeof...(t))
pr(" ");
ps(t...);
}
// DEBUG
void DBG()
{
cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t)
{
cerr << ts(h);
if (sizeof...(t))
cerr << ", ";
DBG(t...);
}
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
// FILE I/O
void setIn(string s)
{
freopen(s.c_str(),"r",stdin);
}
void setOut(string s)
{
freopen(s.c_str(),"w",stdout);
}
void unsyncIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void setIO(string s = "")
{
unsyncIO();
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s))
{
setIn(s+".in"), setOut(s+".out"); // for USACO
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.ans", "w", stdout);
}
setup();
ll n, q;
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];
}
ll ans=0;
for (int t=0; t<7; t++)
{
for (int k=0; k<7; k++)
{
dpl=vector<vector<ll>>(n+3,vector<ll>(n+3,0));
dpr=vector<vector<ll>>(n+3,vector<ll>(n+3,0));
dpb=vector<vector<ll>>(n+3,vector<ll>(n+3,0));
const auto add = [&] (vector<vector<ll>> &dp,ll x,ll y,ll x1,ll y1)
{
dp[x][y]++;
dp[x1+1][y]--;
dp[x][y1+1]--;
dp[x1+1][y1+1]++;
};
for (int i=1; i<=q; i++)
{
bool chk1=(x[i]&(1ll<<t));
bool chk2=(x[i]&(1ll<<k));
if (chk1&&chk2)
{
add(dpb,l[i],l[i],r[i],r[i]);
add(dpl,1,l[i],l[i]-1,r[i]);
add(dpr,l[i],r[i]+1,r[i],n);
}
else if (chk1)
{
add(dpl,l[i],l[i],r[i],n);
}
else if (chk2)
{
add(dpr,1,l[i],r[i],r[i]);
}
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
dpb[i][j]+=dpb[i-1][j];
dpb[i][j]+=dpb[i][j-1];
dpb[i][j]-=dpb[i-1][j-1];
dpl[i][j]+=dpl[i-1][j];
dpl[i][j]+=dpl[i][j-1];
dpl[i][j]-=dpl[i-1][j-1];
dpr[i][j]+=dpr[i-1][j];
dpr[i][j]+=dpr[i][j-1];
dpr[i][j]-=dpr[i-1][j-1];
}
}
const auto get = [&] (ll x,ll parity) ->ll
{
if (x==0) return (parity==0);
return (mod+1)/2;
};
for (int i=1; i<=n; i++)
{
for (int j=i; j<=n; j++)
{
ll nw=(1ll<<(t+k))*i*(n-j+1);
if (i!=j)
nw=(nw*2)%mod;
bool pt=a[i]&(1ll<<t);
bool pt1=a[j]&(1ll<<k);
for (int t1=0;t1<=1;t1++)
{
for (int t2=0;t2<=1;t2++)
{
for (int t3=0;t3<=1;t3++)
{
if ((pt^t1^t3)&&(pt1^t2^t3))
{
ans=(ans+(((get(dpl[i][j],t1)*get(dpr[i][j],t2))%mod*get(dpb[i][j],t3))%mod*nw)%mod)%mod;
}
}
}
}
}
}
}
}
for (int i=1;i<=q;i++)
{
ans=(ans*2)%mod;
}
cout <<ans;
}
Compilation message
xorsum.cpp: In function 'void setIn(std::string)':
xorsum.cpp:277:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
277 | freopen(s.c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
xorsum.cpp: In function 'void setOut(std::string)':
xorsum.cpp:281:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
281 | freopen(s.c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:308:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
308 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:309:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
309 | freopen("test.ans", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
3888 KB |
Output is correct |
| 2 |
Correct |
26 ms |
972 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1720 ms |
32168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
