BZOJ 5000: OI树 题解(倍增)

5000: OI树

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

几天之后小跳蚤即将结束自己在lydsy星球上的旅行。这时,lydsy人却发现他们的超空间传送装置的能量早在小跳
蚤通过石板来到lydsy星球时就已经消耗光了。这时,小跳蚤了解到自己很有可能回不到跳蚤国了,于是掉下了伤
心的眼泪……lydsy人见状决定无论如何也要送小跳蚤回地球,于是lydsy人的大祭司lavendir决定拜访lydsy星球
的OI树,用咒语从OI树中取得能量。咒语中有K种字母,我们用前K个大写英文字母来表示它。OI树可以被认为是一
个有着N个节点的带权有向图,所有节点的出度都是K,并且所有的出边都对应于一个咒语中的字母。仪式开始的时
候有一个标记物放在OI树的1号节点上。之后,从咒语的第一个字母开始,每经过一个字母,标记物就沿着该字母
对应的出边进入这条边的终点,并且得到相当于边权大小的能量值。当咒语处理完毕时,就可以得到这个过程中得
到的所有能量了。现在由于lydsy人超群的计算能力,他们已经知道某咒语大概会获得多少能量,只是还想知道会
获得的能量值对一个数M取模的结果。跳蚤国王通过小跳蚤留下的石板也了解到了小跳蚤现在的处境,所以他又找
到了你,希望你帮助他计算出这个问题的答案。

Input

第一行是两个空格分隔的整数N和K。
之后N行每行2*K个整数A_1,B_1,A_2,B_2,...,A_K,B_K,表示N个节点的K条出边。
第i行表示第 i-1 个节点,这一行的A_S,B_S的值表示第S个大写字母对应的出边的终点为A_S,权值为B_S。
下面一行有一个字符串,表示咒语。
由于咒语的长度会非常长,将采用压缩方式给出,用[SA]表示连续S个字母A,S是一个正整数,A是单个字母。
比如说,字符串[5A]BC[3A][3C]表示的咒语为AAAAABCAAACCC。
之后一个正整数M,表示取模的底数。
字符串长度≤120000,在一个压缩节[SA]中,S≤10^9。K≤26,N≤10000,M≤10^9,所有边的权值小于10^9

Output

一个整数,表示问题的答案。

Sample Input

4 2
3 3 2 5
1 7 3 2
4 3 2 5
2 10 3 2
[3A]B[2A][2B]
10000

Sample Output

38
 
题解
具体来说,
f[i,j,k] 表示从i开始沿着字母j跳2^k次的收益。
g[i,j,k] 表示从i开始沿着字母j跳2^k次后的位置。
显然,得到:
g[i,j,k]=g[g[i,j,k-1],j,k-1];
f[i,j,k]=f[i,j,k-1]+ f[g[i,j,k-1],j,k-1];
预处理O(NKlogMAX)。
然后每一次操作是O(logMAX)。
没了。。。
#include<bits/stdc++.h>
using namespace std;
  
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
    
int buf[30];
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    buf[0]=0;
    while(x)buf[++buf[0]]=x%10,x/=10;
    if(!buf[0])buf[0]=1,buf[1]=0;
    while(buf[0])putchar('0'+buf[buf[0]--]);
    putchar('\n');
}
  
int n,k,A,B,mod,pos,ans;
int f[10005][30][32],g[10005][30][32];
string s;
  
int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            A=read();B=read();
            f[i][j][0]=B;
            g[i][j][0]=A;
        } 
    }
    cin>>s;
    mod=read();
    for(int v=1;v<=30;v++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {
                f[i][j][v]=(f[i][j][v-1]%mod+f[g[i][j][v-1]][j][v-1]%mod)%mod;
                g[i][j][v]=g[g[i][j][v-1]][j][v-1];
            }
        }
    }
    pos=1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='[')
        {
            int p=0;
            while(s[++i]>='0' && s[i]<='9')p=p*10+s[i]-48;
            int r=s[i]-64;
            i++;
            while(p)
            {
                int pv=log2(p);
                (ans+=f[pos][r][pv])%=mod;
                pos=g[pos][r][pv];
                p-=pow(2,pv);
            }
        }
        else
        {
            int r=s[i]-64;
            (ans+=f[pos][r][0])%=mod;
            pos=g[pos][r][0];
        }
    }
    write(ans);
    return 0;
}

  明天就要开学了,又要一段时间不发题解了~ 唔~