QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352828#8335. Fast Hash TransforminstallbWA 31ms505444kbC++143.6kb2024-03-13 17:10:292024-03-13 17:10:30

Judging History

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

  • [2024-03-13 17:10:30]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:505444kb
  • [2024-03-13 17:10:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define M 64
using ull = unsigned long long;
struct Matrix{
    bool A[M][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(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;
    return ret;
}
Matrix Shift(int s){
    Matrix ret;
    for(int i=0;i<64;i++)
        ret.A[i][(i-s+64)%64]=1;
    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(){
    cin>>n>>q>>__C;
    for(int i=1;i<=n;i++){
        scanf("%d",&m);
        for(int j=1;j<=m;j++)
            scanf("%d%d%llu",&s[j],&o[j],&A[j]);
        scanf("%llu",&B);
        Val[i] = Trans();
    }
    T.build(1,n);
    while(q--){
        int op;
        scanf("%d",&op);
        if(op==0){
            int l,r;
            ull x;
            scanf("%d%d%llu",&l,&r,&x);
            printf("%llu\n",T.Query(l,r,x));
        }else{
            int l;
            scanf("%d",&l);
            scanf("%d",&m);
            for(int j=1;j<=m;j++)
                scanf("%d%d%llu",&s[j],&o[j],&A[j]);
            scanf("%llu",&B);
            Val[l] = Trans();
            T.Update(l);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 31ms
memory: 505444kb

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:

51966
18446744073709551615
15
15

result:

wrong answer 1st words differ - expected: '64206', found: '51966'