列表

详情

NC24604. [USACO 2014 Ope G]Code Breaking

描述

The cows keep getting in trouble by taking rides on Farmer John's tractor,
so he has hidden the keys to the tractor in a fancy new safe in his
office. Undeterred, the cows have vowed to try and break into this safe.

The safe is protected by a rather complicated passcode system. The passcode
entry system is arranged as a rooted tree of N (1 <= N <= 20,000) nodes,
each of which requires a digit between 0 and 9. The nodes are indexed 0..N-1.

The only information that the cows have is that certain sequences of length
5 do not occur along particular paths upwards through the tree.

For instance, suppose the tree is the following (rooted at A):

A <- B <- C <- D <- E
^
|
F

The cows might know that the sequence 01234 does not occur starting at F,
and that the sequence 91234 does not occur starting at E. This information
rules out 19 possible passcodes: all those of the form

4 <- 3 <- 2 <- 1 <- *
^
|
0

or

4 <- 3 <- 2 <- 1 <- 9
^
|
*

which gives 19 once we account for the fact that

4 <- 3 <- 2 <- 1 <- 9
^
|
0

appears twice.

Given M (1 <= M <= 50,000) length-5 sequences, together with their starting
nodes in the tree, help the cows figure out how many passcodes have been
ruled out. You should compute your answer modulo 1234567.

输入描述

* Line 1: Two space-separated integers, N and M.

* Lines 2..N: Line i+1 contains a single integer p(i), denoting the
parent of node i in the tree (0 <= p(i) < i).

* Lines N+1..N+M: Line N+i describes the ith sequence known not to
occur in the code.  The line will contain v(i) and s(i)
separated by a space, where v(i) is the starting node of the
sequence, and s(i) is a 5-digit string known not to occur
starting at v(i) and proceeding upward in the tree.  It is
guaranteed that the root is at least 4 steps upward from v(i).

输出描述

* Line 1: A single integer giving the number of ruled-out
configurations, modulo 1234567.

示例1

输入: 

6 2
0
1
2
3
3
4 01234
5 91234

输出: 

19

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 547ms, 内存消耗: 24036K, 提交时间: 2020-03-07 11:37:45 

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef map<int,int>T;
const int N=20010,M=860000,MAXN=2100000,U=300010,P=1234567;
int n,m,i,j,x,y,g[N],nxt[N],sub[M],right[M],ans;char ch[9];
T f[N];T::iterator k;int tmp[U],tag[MAXN];bool s[MAXN];
struct E{int x,y;E(){}E(int _x,int _y){x=_x,y=_y;}}q[U],e[U*2];
inline bool cmp(const E&a,const E&b){return a.x<b.x;}
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline void tag1(int x,int p){tag[x]=1LL*tag[x]*p%P;}
inline void pb(int x){if(tag[x]!=1)tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=1;}
void build(int x,int a,int b){
  if(a==b)return;
  tag[x]=1;
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
void ins(int x,int a,int b,int c,int p){
  if(a==b){
    up(tag[x],p);
    s[x]=!!tag[x];
    return;
  }
  pb(x);
  int mid=(a+b)>>1;
  if(c<=mid)ins(x<<1,a,mid,c,p);else ins(x<<1|1,mid+1,b,c,p);
  s[x]=s[x<<1]|s[x<<1|1];
}
void change(int x,int a,int b,int c,int d,int p){
  if(c<=a&&b<=d){tag1(x,p);return;}
  pb(x);
  int mid=(a+b)>>1;
  if(c<=mid)change(x<<1,a,mid,c,d,p);
  if(d>mid)change(x<<1|1,mid+1,b,c,d,p);
}
int ask(int x,int a,int b,int c){
  if(a==b)return tag[x];
  pb(x);
  int mid=(a+b)>>1;
  return c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);
}
void dfs(int x,int a,int b,T&f){
  if(!s[x])return;
  if(a==b){
    if(tag[x])up(f[a<<4&1048575],tag[x]);
    tag[x]=s[x]=0;
    return;
  }
  pb(x);
  int mid=(a+b)>>1;
  dfs(x<<1,a,mid,f),dfs(x<<1|1,mid+1,b,f);
  s[x]=0;
}
inline void solve(){
  int i,j,cnt=0,s=0;
  for(i=0;i<m;i++){
    tmp[i]=0;
    for(j=sub[q[i].x];~j;j=sub[j])up(tmp[i],ask(1,0,M,j));
    e[++cnt]=E(q[i].x,q[i].y);
    e[++cnt]=E(right[q[i].x],P-q[i].y);
  }
  sort(e+1,e+cnt+1,cmp);
  for(i=1;i<=cnt;i++){
    if(i>1&&e[i].x>e[i-1].x)change(1,0,M,e[i-1].x,e[i].x-1,s);
    up(s,e[i].y);
  }
  for(i=0;i<m;i++)if(tmp[i])ins(1,0,M,q[i].x,1LL*q[i].y*tmp[i]%P);
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=2;i<=n;i++)scanf("%d",&x),nxt[i]=g[++x],g[x]=i;
  while(m--){
    scanf("%d%s",&x,ch);
    for(y=j=0;j<5;j++)y=y<<4|(ch[j]-'0'+1);
    f[x+1][y]=P-1;
  }
  for(sub[0]=-1,right[0]=M,i=1;i<M;i++)for(j=0;;j++)if(i>>(j*4)&15){
    sub[i]=i-(((i>>(j*4))&15)<<(j*4));
    right[i]=i+(1<<(j*4));
    break;
  }
  build(1,0,M);
  for(i=n;i;i--){
    for(j=1;j<=10;j++)f[i][j<<16]=1;
    for(k=f[i].begin();k!=f[i].end();k++)ins(1,0,M,k->first,k->second);
    for(j=g[i];j;j=nxt[j]){
      m=0;
      for(k=f[j].begin();k!=f[j].end();k++)q[m++]=E(k->first,k->second);
      solve();
    }
    f[i].clear();
    dfs(1,0,M,f[i]);
  }
  for(ans=i=1;i<=n;i++)ans=ans*10%P;
  up(ans,P-f[1][0]);
  return printf("%d",ans),0;
}

上一题

© 2024 nowcoder.com