/ @@18khV /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 15ms 22.602 MiB
#2 Accepted 15ms 22.699 MiB
#3 Accepted 14ms 22.656 MiB
#4 Accepted 14ms 20.551 MiB
#5 Accepted 278ms 191.363 MiB
#6 Accepted 297ms 191.496 MiB
#7 Accepted 178ms 191.328 MiB
#8 Accepted 197ms 191.234 MiB
#9 Accepted 532ms 192.387 MiB
#10 Accepted 535ms 192.332 MiB
#11 Accepted 172ms 189.52 MiB
#12 Accepted 189ms 189.734 MiB
#13 Accepted 171ms 189.754 MiB
#14 Accepted 174ms 189.426 MiB
#15 Accepted 181ms 189.395 MiB
#16 Accepted 765ms 189.855 MiB
#17 Accepted 749ms 189.863 MiB
#18 Accepted 667ms 190.008 MiB
#19 Accepted 701ms 189.93 MiB
#20 Accepted 653ms 189.953 MiB

代码

#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;
}

信息

递交者
类型
递交
题目
P1016 切树游戏
题目数据
下载
语言
C++
递交时间
2020-07-23 17:17:30
评测时间
2020-07-23 17:17:30
评测机
分数
100
总耗时
6507ms
峰值内存
192.387 MiB