QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352876#8335. Fast Hash TransforminstallbTL 2091ms155464kbC++204.1kb2024-03-13 17:36:442024-03-13 17:36:44

Judging History

你现在查看的是最新测评结果

  • [2024-03-13 17:36:44]
  • 评测
  • 测评结果:TL
  • 用时:2091ms
  • 内存:155464kb
  • [2024-03-13 17:36:44]
  • 提交

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);
}
bool cnt[1<<16];
void Init(){
    for(int i=1;i<1<<16;i++)
        cnt[i] = cnt[i^(i&-i)]^1;
}
const ull BB = (1<<16)-1;
inline bool COUNT(const ull &x){
    return cnt[x&BB]^cnt[(x>>16)&BB]^cnt[(x>>32)&BB]^cnt[(x>>48)&BB];
}
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]=COUNT(u[i]&res.v[j]);
        ret.get();
        return ret;
    }
    Matrix operator + (const Matrix &res)const{
        Matrix ret;
        for(int i=0;i<M;i++){
            ret.A[i]=A[i]^res.A[i];
            ret.u[i]=u[i]^res.u[i];
            ret.v[i]=v[i]^res.v[i];
        }
        return ret;
    }
    ull operator & (const ull &res)const{
        ull ret = 0;
        for(int i=0;i<M;i++)
            ret ^= ((ull)(COUNT(u[i]&res))<<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.u[i]|=1ull<<i;
            ret.v[i]|=1ull<<i;
        }
    return ret;
}
Matrix Shift(int s){
    Matrix ret;
    for(int i=0;i<64;i++){
        ret.A[i][(i-s+64)%64]=1;
        ret.u[i]|=1ull<<(i-s+64)%64;
        ret.v[(i-s+64)%64]|=1ull<<i;
    }
    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(){
    Init();
    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: 4ms
memory: 155376kb

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: 25ms
memory: 155376kb

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: 172ms
memory: 155464kb

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: 555ms
memory: 155364kb

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: 0
Accepted
time: 2091ms
memory: 155348kb

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 ...

output:

11875257514484243925
3443357416933857062
16160011677622853538
1582145987019406393
15019762274690743371
3128972641411454448
10632018957963074870
2420532366876270818
16130728863118353230
15834956073901517645
18404809296474853851
10982435108266120760
16463778300806795274
11990886156320593058
1145171640...

result:

ok 19600 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

20000 20000 0
34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...

output:


result: