题解

2 条题解

  • 2
    @ 2017-11-08 21:02:58
    #include<cstdio>
    const int N=30010,M=65540,V=128+1,P=10007,INV=(P+1)/2;
    char op[9];
    int n,m,Q,i,j,x,y,g[N],v[N<<1],nxt[N<<1],ed,inv[P];
    int size[N],f[N],son[N],top[N],bottom[N],loc[N],q[N],dfn;
    int a[N][V],dp[N][V],h[N][V],c[N][V],ans[V],ret[V];
    struct E{int sum[V],pre[V],suf[V],mul[V];}val[M],tmp;
    bool flag;
    inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    inline void FWT(int*a,int n){
      for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
        int x=a[i+j],y=a[i+j+d];
        a[i+j]=(x+y)%P;
        a[i+j+d]=(x-y+P)%P;
      }
    }
    inline void UFWT(int*a,int n){
      for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
        int x=a[i+j],y=a[i+j+d];
        a[i+j]=(x+y)*INV%P;
        a[i+j+d]=(x-y+P)*INV%P;
      }
    }
    void dfs(int x){
      size[x]=1;
      for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
        f[v[i]]=x;
        dfs(v[i]);
        size[x]+=size[v[i]];
        if(size[v[i]]>size[son[x]])son[x]=v[i];
      }
    }
    void dfs2(int x,int y){
      q[loc[x]=++dfn]=x;
      top[x]=y;
      bottom[y]=x;
      if(son[x])dfs2(son[x],y);
      for(int i=0;i<m;i++)h[x][i]=1,c[x][i]=0;
      for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]&&v[i]!=son[x]){
        int u=v[i];
        dfs2(u,u);
        for(int j=0;j<m;j++){
          if(dp[u][j]+1<P)h[x][j]=h[x][j]*(dp[u][j]+1)%P;
          else c[x][j]++;
        }
      }
      for(int i=0;i<m;i++){
        if(c[x][i])dp[x][i]=0;
        else dp[x][i]=a[x][i]*h[x][i]%P*(dp[son[x]][i]+1)%P;
        ans[i]=(ans[i]+dp[x][i])%P;
      }
    }
    inline void init(E&x,int p){
      for(int i=0;i<m;i++){
        if(c[p][i])x.sum[i]=x.pre[i]=x.suf[i]=x.mul[i]=0;
        else x.sum[i]=x.pre[i]=x.suf[i]=x.mul[i]=a[p][i]*h[p][i]%P;
      }
    }
    inline void merge(E&f,const E&l,const E&r){
      for(int i=0;i<m;i++){
        f.sum[i]=(l.sum[i]+r.sum[i]+l.suf[i]*r.pre[i])%P;
        f.pre[i]=(l.pre[i]+l.mul[i]*r.pre[i])%P;
        f.suf[i]=(r.suf[i]+r.mul[i]*l.suf[i])%P;
        f.mul[i]=l.mul[i]*r.mul[i]%P;
      }
    }
    void build(int x,int a,int b){
      if(a==b){init(val[x],q[a]);return;}
      int mid=(a+b)>>1;
      build(x<<1,a,mid),build(x<<1|1,mid+1,b);
      merge(val[x],val[x<<1],val[x<<1|1]);
    }
    void change(int x,int a,int b,int c){
      if(a==b){init(val[x],q[a]);return;}
      int mid=(a+b)>>1;
      if(c<=mid)change(x<<1,a,mid,c);else change(x<<1|1,mid+1,b,c);
      merge(val[x],val[x<<1],val[x<<1|1]);
    }
    void ask(int x,int a,int b,int c,int d){
      if(c<=a&&b<=d){
        if(!flag)tmp=val[x],flag=1;
        else merge(tmp,tmp,val[x]);
        return;
      }
      int mid=(a+b)>>1;
      if(c<=mid)ask(x<<1,a,mid,c,d);
      if(d>mid)ask(x<<1|1,mid+1,b,c,d);
    }
    inline void modify(int x){
      while(x){
        int y=f[top[x]];
        flag=0;
        ask(1,1,n,loc[top[x]],loc[bottom[top[x]]]);
        for(int i=0;i<m;i++)ans[i]=(ans[i]-tmp.sum[i]+P)%P;
        if(y)for(int i=0;i<m;i++){
          if(tmp.pre[i]+1<P)h[y][i]=h[y][i]*inv[tmp.pre[i]+1]%P;
          else c[y][i]--;
        }
        change(1,1,n,loc[x]);
        flag=0;
        ask(1,1,n,loc[top[x]],loc[bottom[top[x]]]);
        for(int i=0;i<m;i++)ans[i]=(ans[i]+tmp.sum[i])%P;
        if(y)for(int i=0;i<m;i++){
          if(tmp.pre[i]+1<P)h[y][i]=h[y][i]*(tmp.pre[i]+1)%P;
          else c[y][i]++;
        }
        x=y;
      }
    }
    int main(){
      for(inv[0]=inv[1]=1,i=2;i<P;i++)inv[i]=(P-inv[P%i])*(P/i)%P;
      scanf("%d%d",&n,&m);
      for(i=1;i<=n;i++){
        scanf("%d",&x);
        for(j=0;j<m;j++)a[i][j]=0;
        a[i][x]=1;
        FWT(a[i],m);
      }
      for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
      dfs(1);
      dfs2(1,1);
      build(1,1,n);
      scanf("%d",&Q);
      while(Q--){
        scanf("%s%d",op,&x);
        if(op[0]=='C'){
          scanf("%d",&y);
          for(i=0;i<m;i++)a[x][i]=0;
          a[x][y]=1;
          FWT(a[x],m);
          modify(x);
        }else{
          for(i=0;i<m;i++)ret[i]=ans[i];
          UFWT(ret,m);
          printf("%d\n",ret[x]);
        }
      }
      return 0;
    }
    
  • 1
    @ 2020-08-08 20:34:04
    #pragma G++ optimize(2)
    #pragma GCC optimize(2)
    #include<bits/stdc++.h>
    #define LL long long
    #define O4 __inline__ __attribute__((always_inline))
    #define inf 0x7fffffff
    #define UL unsigned LL
    #define LD long double
    #ifdef ONLINE_JUDGE
    #define getchar nc
    #endif
    //#define int LL
    namespace FastIO{
        O4 char nc(){
            static char buf[100000],*p1=buf,*p2=buf;
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
        }
        O4 int read(){
            char t;int u=0,k=1;t=getchar();
            while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
            while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
            return u*k;
        }
        template <typename T>
        O4 void read(T &u){
            char t;T k=1;u=0;t=getchar();
            while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
            while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
            if(t=='.'){
                T mass=0.1;t=getchar();
                while(t>='0'&&t<='9'){u+=mass*(t-'0');mass/=10;t=getchar();}
            }u*=k;
        }
        O4 int read(char asd[]){
            char t=getchar();int u=0;
            while(t==' '||t=='\n'||t=='\r')t=getchar();
            if(t==EOF)return -1;
            while(t!=' '&&t!='\n'&&t!=EOF&&t!='\r')asd[u++]=t,t=getchar();
            asd[u]='\0';return u;
        }
        char sr[1<<23],z[23];int C=-1,Z;
        O4 void wer(int x,char T){
            int y=0;if(x<0)y=1,x=-x;
            while(z[++Z]=x%10+'0',x/=10);if(y)z[++Z]='-';
            while(sr[++C]=z[Z],--Z);sr[++C]=T;
        }
        O4 void wer(char T[],char QWQ){
            for(int i=0;T[i]!='\0';i++)sr[++C]=T[i];
            sr[++C]=QWQ;
        }
        O4 void out(){fwrite(sr,1,C+1,stdout);C=-1;}
    }
    using namespace std;
    using namespace FastIO;
    namespace whatever{
        const int mod=10007;
        const int inv_2=(mod+1)/2;
        vector<int> adj[30001];
        int heavy[30001];
        int size[30001];
        int father[30001];
        void dfs1(int cur, int father){
            size[cur]=1;
            heavy[cur]=-1;
            for(size_t i=0; i<adj[cur].size(); ++i){
                int to=adj[cur][i];
                if(to==father)
                    continue;
                whatever::father[to]=cur;
                dfs1(to, cur);
                if(heavy[cur]==-1||size[heavy[cur]]<size[to])
                    heavy[cur]=to;
                size[cur]+=size[to];
            }
        }
        struct node_type{
            node_type *left, *right;
            node_type *father;
            short result[128];
            short all[128];
            union{
                struct{
                    short prefix[128];
                    short suffix[128];
                };
                struct{
                    short cnt[128];
                    short all_without_cnt[128];
                };
            };
        };
        node_type nodes[30000*2];
        int node_cnt;
        node_type *allocate(){
            return &nodes[node_cnt++];
        }
        int init_value[30001];
        int light_size[30001];
        int prefix_sum[30001];
        int path[30001];
        node_type *root;
        int m;
        void push_up(node_type *cur){
            node_type *left=cur->left;
            node_type *right=cur->right;
            short *left_prefix=(left->left?left->prefix:left->all);
            short *right_suffix(right->left?right->suffix:right->all);
            short *left_suffix=(left->left?left->suffix:left->all);
            short *right_prefix=(right->left?right->prefix:right->all);
            #if 0//<-----------------------------
            for(int i=0; i<m; ++i)
                cur->prefix[i]=(left->prefix[i]+right->prefix[i]*left->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->suffix[i]=(right->suffix[i]+left->suffix[i]*right->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->all[i]=(left->all[i]*right->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->result[i]=(left->result[i]+right->result[i]+left->suffix[i]*right->prefix[i])%mod;
            #endif
            for(int i=0; i<m; ++i)
                cur->prefix[i]=(left_prefix[i]+right_prefix[i]*left->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->suffix[i]=(right_suffix[i]+left_suffix[i]*right->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->all[i]=(left->all[i]*right->all[i])%mod;
            for(int i=0; i<m; ++i)
                cur->result[i]=(left->result[i]+right->result[i]+left_suffix[i]*right_prefix[i])%mod;
        }
        int popcount_table[128];
        node_type *build(int first, int last){
            if(first==last){
                node_type *cur=&nodes[path[first]];
                //memcpy(cur->result, cur->all, sizeof(short)*m);
                //xxx
                int value=init_value[path[first]];
                for(int i=0; i<m; ++i){
                    int sign=(popcount_table[value&i]&1?mod-1:1);
                    cur->all_without_cnt[i]=cur->all_without_cnt[i]*sign%mod;
                    if(cur->cnt[i])
                        cur->all[i]=0;
                    else
                        cur->all[i]=cur->all_without_cnt[i];
                    cur->result[i]=(cur->result[i]+cur->all[i])%mod;
                }
                return cur;
            }
            int mid=lower_bound(prefix_sum+first, prefix_sum+last-1, prefix_sum[first-1]+(prefix_sum[last]-prefix_sum[first-1])/2)-prefix_sum;
            assert(mid>=first);
            assert(mid<last);
            node_type *cur=allocate();
            cur->left=build(first, mid);
            cur->left->father=cur;
            cur->right=build(mid+1, last);
            cur->right->father=cur;
            push_up(cur);
            return cur;
        }
        int top[30001];
        void dfs2(int cur, int father){
            for(size_t i=0; i<adj[cur].size(); ++i){
                int to=adj[cur][i];
                if(to==father)
                    continue;
                if(to==heavy[cur])
                    continue;
                top[to]=to;
                dfs2(to, cur);
            }
            light_size[cur]=size[cur];
            if(heavy[cur]!=-1){
                light_size[cur]-=size[heavy[cur]];
                top[heavy[cur]]=top[cur];
                dfs2(heavy[cur], cur);
            }
            else{
                cur=top[cur];
                father=whatever::father[cur];
                int len=0;
                do{
                    path[++len]=cur;
                    prefix_sum[len]=prefix_sum[len-1]+light_size[cur];
                    cur=heavy[cur];
                }
                while(cur!=-1);
                node_type *node=build(1, len);
                if(father==-1)
                    root=node;
                else{
                    node->father=&nodes[father];
                    for(int i=0; i<m; ++i)
                        nodes[father].result[i]=(nodes[father].result[i]+node->result[i])%mod;
                    if(node->left){
                        for(int i=0; i<m; ++i)
                            if(node->prefix[i]+1!=mod)
                                nodes[father].all_without_cnt[i]=nodes[father].all_without_cnt[i]*(node->prefix[i]+1)%mod;
                            else
                                ++nodes[father].cnt[i];
                    }
                    else{
                        for(int i=0; i<m; ++i)
                        //  if(node->all[i]+1!
                            if(node->all[i]+1!=mod)
                                nodes[father].all_without_cnt[i]=nodes[father].all_without_cnt[i]*(node->all[i]+1)%mod;
                            else
                                ++nodes[father].cnt[i];
                    }
                }
            }
        }
        int inv[mod];
        void update_leaf(node_type *cur, short *old_result, short *new_result, short *old_prefix_or_all, short *new_prefix_or_all){
            assert(!cur->left);
            for(int i=0; i<m; ++i){
                if(old_prefix_or_all[i] +1/*<------------*/!=mod)
                    cur->all_without_cnt[i]=cur->all_without_cnt[i]*inv[old_prefix_or_all[i] +1/*<------------*/]%mod;
                else{
                    assert(cur->cnt[i]>0);
                    --cur->cnt[i];
                }
                if(new_prefix_or_all[i] +1/*<------------*/!=mod)
                    cur->all_without_cnt[i]=cur->all_without_cnt[i]*(new_prefix_or_all[i] +1/*<------------*/)%mod;
                else
                    ++cur->cnt[i];
                int old_all=cur->all[i];
                if(cur->cnt[i])
                    cur->all[i]=0;
                else
                    cur->all[i]=cur->all_without_cnt[i];
                cur->result[i]=(cur->result[i]-old_all+cur->all[i]-old_result[i]+new_result[i]+mod*2)%mod;
            }
        }
        void run(){
            int n=read();m=read();
            for(int i=1; i<128; ++i)
                popcount_table[i]=popcount_table[i-(i&-i)]+1;
            inv[1]=1;
            for(int i=2; i<mod; ++i)
                inv[i]=(mod-mod/i)*inv[mod%i]%mod;
            for(int i=1; i<=n; ++i)
                init_value[i]=read();
            for(int i=1; i<n; ++i){
                int a=read();
                int b=read();
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
            father[1]=-1;
            dfs1(1, -1);
            top[1]=1;
            node_cnt=n+1;
            for(int i=1; i<=n; ++i)
                for(int j=0; j<m; ++j)
                    nodes[i].all_without_cnt[j]=1;
            dfs2(1, -1);
            int q=read();//30000
            while(--q!=-1){
                char ch=getchar();
                while(!isupper(ch))
                    ch=getchar();
                if(ch=='C'){//10000
                    int x=read();
                    int y=read();
                    node_type *cur=&nodes[x];
                    static short old_result[128];
                    static short old_prefix_or_all[128];
                    node_type *prev;
                    while(cur){
                        if(cur->father&&!cur->father->left&&(cur->left||cur==&nodes[x])){
                            memcpy(old_result, cur->result, sizeof(short)*m);
                            memcpy(old_prefix_or_all, (cur==&nodes[x]?cur->all:cur->prefix), sizeof(short)*m);
                        }
                        if(cur==&nodes[x]){
                            int value=init_value[x];
                            for(int i=0; i<m; ++i){
                                if((popcount_table[value&i]&1)==(popcount_table[y&i]&1))
                                    continue;
                                cur->all_without_cnt[i]=mod-cur->all_without_cnt[i];
                                if(cur->cnt[i])
                                    continue;
                                cur->result[i]=(cur->result[i]-cur->all[i]*2+mod*2)%mod;
                                cur->all[i]=cur->all_without_cnt[i];
                            }
                        }
                        else if(cur->left)
                            push_up(cur);
                        else{
                            update_leaf(cur, old_result, prev->result, old_prefix_or_all, (prev==&nodes[x]?prev->all:prev->prefix));
                        }
                        prev=cur;
                        cur=cur->father;
                    }
                    init_value[x]=y;
                }
                else if(ch=='Q'){
                    int k=read();
                    int result=0;
                    for(int i=0; i<m; ++i){
                        int sign=(popcount_table[i&k]&1?-1:1);
                        result+=root->result[i]*sign;
                    }
                    result=(result%mod+mod)%mod;
                    result=result*inv[m]%mod;
                    wer(result,'\n');
                }
                else
                    assert(0);
            }
        }
    }
    int main(){
        whatever::run();out();
    }
    
  • 1

信息

ID
2021
难度
5
分类
(无)
标签
递交数
23
已通过
12
通过率
52%
被复制
2
上传者