#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ci = const int;
using ll = long long;
template <typename T>
constexpr bool test(const T x,ci p){return (x >> p) & 1;}
constexpr int mod = 998244353;
constexpr int add(const int a,const int b){return a + b >= mod ? a + b - mod : a + b;}
template <typename ...Args>
constexpr int add(const int a,const int b,const Args... args){return add(add(a,b),args...);}
constexpr int sub(const int a,const int b){return a >= b ? a - b : a - b + mod;}
constexpr int mul(const int a,const int b){return 1ll * a * b % mod;}
template <typename ...Args>
constexpr int mul(const int a,const int b,const Args... args){return mul(mul(a,b),args...);}
constexpr int sgn(const int x,const int p){return (p & 1) ? mod - x : x;}
template <typename T>
int qpow(int base,T b,int res = 1){
while(b){
if(b & 1)res = mul(res,base);
base = mul(base,base);
b >>= 1;
}
return res;
}
int inv(const int x){return qpow(x,mod - 2);}
void addeq(int &x,const int y){if((x += y) >= mod)x -= mod;}
void subeq(int &x,const int y){if((x -= y) < 0)x += mod;}
void muleq(int &x,const int y){x = mul(x,y);}
constexpr int maxn = 1003,maxq = 1e5 + 100,maxk = 7;
int val[maxn],pw[maxq],sum[maxk][maxk][2][2][maxn][maxn],n,q;
int f(ci n,ci o){
if(n == 0)return !o;
return pw[n - 1];
}
int query(ci k1,ci k2,ci o1,ci o2,ci xl,ci xr,ci yl,ci yr){
if(xl > xr || yl > yr)return 0;
let &sum = ::sum[k1][k2][o1][o2];
return sum[xr][yr] - sum[xr][yl - 1] - sum[xl - 1][yr] + sum[xl - 1][yl - 1];
}
int main(){
// std::freopen("sample2.in","r",stdin);
std::scanf("%d %d",&n,&q);
rep(i,1,n)std::scanf("%d",val + i);
repn(q){
int l,r,v; std::scanf("%d %d %d",&l,&r,&v);
rep(k0,0,maxk - 1)
rep(k1,0,maxk - 1)
sum[k0][k1][test(v,k0)][test(v,k1)][l][r]++;
}
rep(k0,0,maxk - 1)
rep(k1,0,maxk - 1)
for(let o1 : {0,1})
for(let o2 : {0,1}){
auto &sum = ::sum[k0][k1][o1][o2];
rep(i,1,n)
rep(j,1,n)
sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
pw[0] = 1;
rep(i,1,q){
pw[i] = pw[i - 1] << 1;
if(pw[i] >= mod)pw[i] -= mod;
}
int ans = 0;
rep(x,1,n)
rep(y,x,n){
int coef = x * (n - y + 1);
if(x != y)coef *= 2;
rep(k1,0,maxk - 1)
rep(k2,0,maxk - 1){
int cnt[2][2]{};
for(let o1 : {0,1})
for(let o2 : {0,1}){
let x1 = query(k1,k2,o1,o2,1,x,y,n);
int x2 = query(k1,k2,o1,o2,1,x,x,n);
int x3 = query(k1,k2,o1,o2,1,y,y,n);
x2 -= x1;
x3 -= x1;
cnt[o1][o2] += x1;
cnt[o1][0] += x2;
cnt[0][o2] += x3;
cnt[0][0] += q - x1 - x2 - x3;
}
{
int v = mul(coef,1 << k1,1 << k2,pw[cnt[0][0]],f(cnt[1][1],0));
muleq(v,f(cnt[1][0],test(val[x],k1) ^ 1));
muleq(v,f(cnt[0][1],test(val[y],k2) ^ 1));
addeq(ans,v);
}
{
int v = mul(coef,1 << k1,1 << k2,pw[cnt[0][0]],f(cnt[1][1],1));
muleq(v,f(cnt[1][0],test(val[x],k1)));
muleq(v,f(cnt[0][1],test(val[y],k2)));
addeq(ans,v);
}
}
}
std::printf("%d\n",ans);
return 0;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:56:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | std::scanf("%d %d",&n,&q);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:57:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | rep(i,1,n)std::scanf("%d",val + i);
| ~~~~~~~~~~^~~~~~~~~~~~~~
xorsum.cpp:60:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | int l,r,v; std::scanf("%d %d %d",&l,&r,&v);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
78144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
321 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
