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

正解:倍增。

比较裸的题,直接对于每一段路,倍增算出答案即可。

 #include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long using namespace std; int f[][][],v[][][],n,k,len,rhl,ans;
char s[]; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} int main(){
#ifndef ONLINE_JUDGE
freopen("OItree.in","r",stdin);
freopen("OItree.out","w",stdout);
#endif
n=gi(),k=gi();
for (RG int i=;i<=n;++i)
for (RG int j=;j<k;++j)
f[j][][i]=gi(),v[j][][i]=gi();
scanf("%s",s+),len=strlen(s+),rhl=gi();
for (RG int p=;p<k;++p)
for (RG int j=;j<=;++j)
for (RG int i=;i<=n;++i){
f[p][j][i]=f[p][j-][f[p][j-][i]];
v[p][j][i]=v[p][j-][f[p][j-][i]]+v[p][j-][i];
if (v[p][j][i]>=rhl) v[p][j][i]-=rhl;
}
for (RG int i=,jp,p,S=;i<=len;){
while (s[i]=='[') ++i; jp=;
while (s[i]>='' && s[i]<='') jp=jp*+s[i]-,++i;
if (!jp) jp=; p=s[i]-'A',++i; while (s[i]==']') ++i;
for (RG int j=;j>=;--j)
if (jp>=(<<j)){
jp-=<<j,ans+=v[p][j][S],S=f[p][j][S];
if (ans>=rhl) ans-=rhl;
}
if (i>len) break;
}
cout<<ans; return ;
}
05-11 19:21