本文共 1607 字，大约阅读时间需要 5 分钟。

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

题意

就是说对于每个节点，告诉你从这个点走向第i个字母后的节点是哪一个，还有这条边的边权

然后给你一个字符串，你一开始在1这个起点，开始走，问题代价

题解

倍增一下就好了

#include
   
    #include
    
     const int N=10005;int n,k;int to[N][28][32],v[N][28][32],MOD;char ss[120010];int now=1,ans=0;void shen (int x,int y){//  printf("%d %d %d %d\n",x,y,ans,now);    for (int u=30;u>=0;u--)        if (x>=(1<
     
      ='0'&&ss[u+1]<='9')                u++,sum=sum*10+(ss[u]-'0');            shen(sum,ss[u+1]-'A'+1);            u+=2;        }        else         {        //  printf("%d %d\n",now,ss[u]-'A');            ans=(ans+v[now][ss[u]-'A'+1][0])%MOD,now=to[now][ss[u]-'A'+1][0];        }    }    printf("%d\n",ans);    return 0;}