QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352845 | #8335. Fast Hash Transform | installb | TL | 1157ms | 155376kb | C++14 | 3.8kb | 2024-03-13 17:21:57 | 2024-03-13 17:21:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define M 64
using ull = unsigned long long;
template<class T>void Rd(T &x){
static char c;
while(c=getchar(),!isdigit(c));
for(x=0;isdigit(c);c=getchar())
x=(x<<1)+(x<<3)+(c^48);
}
struct Matrix{
bitset<M>A[M];
ull u[M],v[M];
void get(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
u[i] |= (ull)(A[i][j])<<j;
v[j] |= (ull)(A[i][j])<<i;
}
}
Matrix operator * (const Matrix &res)const{
Matrix ret;
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
ret.A[i][j]=__builtin_popcountll(u[i]&res.v[j])&1;
ret.get();
return ret;
}
Matrix operator + (const Matrix &res)const{
Matrix ret;
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
ret.A[i][j]=A[i][j]^res.A[i][j];
}
ret.get();
return ret;
}
ull operator & (const ull &res)const{
ull ret = 0;
for(int i=0;i<M;i++)
ret ^= ((ull)(__builtin_popcountll(u[i]&res)&1)<<i);
return ret;
}
Matrix(){
memset(u,0,sizeof(u));
memset(v,0,sizeof(v));
memset(A,0,sizeof(A));
}
};
struct Node{
Matrix k;
ull b;
Node(){}
Node(Matrix aa,ull bb):k(aa),b(bb){}
Node operator + (const Node &res)const{
return Node(k*res.k,(k&res.b)^b);
}
ull Ask(ull x){
return ((k&x)^b);
}
}Val[20005];
struct Seg{
struct TNODE{
int l,r;
Node v;
}tree[20005<<2];
#define fa tree[p]
#define lson tree[p<<1]
#define rson tree[p<<1|1]
int pos[20005];
void Up(int p){
fa.v = rson.v + lson.v;
}
void build(int l,int r,int p=1){
fa.l=l,fa.r=r;
if(l==r){
pos[l]=p;
fa.v=Val[l];
return;
}
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
Up(p);
}
void Update(int x){
int p = pos[x];
fa.v = Val[x];
for(int i=p>>1;i;i>>=1)Up(i);
}
ull Query(int l,int r,ull x,int p=1){
if(l==fa.l && r==fa.r)return fa.v.Ask(x);
int mid=fa.l+fa.r>>1;
if(r<=mid)return Query(l,r,x,p<<1);
else if(l>mid)return Query(l,r,x,p<<1|1);
else return Query(mid+1,r,Query(l,mid,x,p<<1),p<<1|1);
}
#undef fa
#undef lson
#undef rson
}T;
int m,s[20005];
ull A[20005],B;
int o[20005];
Matrix AND(ull p){
Matrix ret;
for(int i=0;i<64;i++)
if((1ull<<i)&p)ret.A[i][i]=1;
ret.get();
return ret;
}
Matrix Shift(int s){
Matrix ret;
for(int i=0;i<64;i++)
ret.A[i][(i-s+64)%64]=1;
ret.get();
return ret;
}
const ull BS = -1;
Node Trans(){
Matrix k;
ull b = 0;
for(int i=1;i<=m;i++){
if(o[i] == 1) k = k + (AND(A[i])*Shift(s[i]));
else k = k + (AND(A[i]^BS)*Shift(s[i]));
if(!o[i]) b ^= (AND(A[i])&BS);
}
b ^= B;
return Node(k,b);
}
int n,q,__C;
int main(){
Rd(n),Rd(q),Rd(__C);
for(int i=1;i<=n;i++){
Rd(m);
for(int j=1;j<=m;j++)
Rd(s[j]),Rd(o[j]),Rd(A[j]);
Rd(B);
Val[i] = Trans();
}
T.build(1,n);
while(q--){
int op;Rd(op);
if(op==0){
int l,r;
ull x;
Rd(l),Rd(r),Rd(x);
printf("%llu\n",T.Query(l,r,x));
}else{
int l;
Rd(l),Rd(m);
for(int j=1;j<=m;j++)
Rd(s[j]),Rd(o[j]),Rd(A[j]);
Rd(B);
Val[l] = Trans();
T.Update(l);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 155284kb
input:
3 5 1 1 4 0 0 51966 1 60 0 0 0 1 0 0 16 15 0 1 1 771 0 2 2 32368 0 3 3 0 1 2 2 0 0 15 61 1 4095 46681 0 1 3 2023
output:
64206 2023 31 1112
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 27ms
memory: 155296kb
input:
9 9 3 32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...
output:
9487331362121050549 3906661590723083106 15757672015979182109 4975471776251039345 11503109206538591140 3763610618439604410
result:
ok 6 tokens
Test #3:
score: 0
Accepted
time: 455ms
memory: 155376kb
input:
1 20000 400 32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...
output:
11827781865759498816 7454610526276185721 9581050724293785387 2177163806257271094 14004004964877510141 18073834598135159471 16966489063087641088 12289032565388413023 17823140805867698239 18104549908461644670 15570008264282957124 12400954982104000299 9842549278742638708 16535034933613060362 1561642006...
result:
ok 19600 tokens
Test #4:
score: 0
Accepted
time: 1157ms
memory: 155372kb
input:
500 20000 400 32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...
output:
9119093329811149961 16901643057538871933 17161855998497876349 3964234071281411558 13588188063229334268 15557968976322375381 4612345875926431452 9507168112801039022 9504318642653891468 217407202160767706 12982350345598971306 17957502630817476223 6353877977318728572 15552768639781831485 16778108770682...
result:
ok 19600 tokens
Test #5:
score: -100
Time Limit Exceeded
input:
4000 20000 400 35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...