[bzoj5000][乱搞]OI树

本文主要是介绍[bzoj5000][乱搞]OI树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题解

设$nxt[i][j][k]$表示走第i条路 往下走$2^j$长度 在第k个点会到达哪个点
顺便预处理一下路径前缀和
大力倍增一下…
就没了啊

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#define LL long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int read()
{int f=1,x=0;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;
}
inline void write(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
int mod,n,K;
int bin[35],nxt[27][35][10005],S[27][35][10005]; 
void ad(int &x,int y){x+=y;if(x>mod)x-=mod;}
char ch[120005];
int main()
{n=read();K=read();bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;for(int i=1;i<=n;i++)for(int j=1;j<=K;j++)nxt[j][0][i]=read(),S[j][0][i]=read();scanf("%s",ch+1);int len=strlen(ch+1);mod=read();	for(int i=1;i<=30;i++)for(int j=1;j<=n;j++)for(int k=1;k<=K;k++){nxt[k][i][j]=nxt[k][i-1][nxt[k][i-1][j]];S[k][i][j]=(S[k][i-1][j]+S[k][i-1][nxt[k][i-1][j]])%mod;}int pos=1,nt,ans=0;for(int i=1;i<=len;i=nt){if(ch[i]>='A'&&ch[i]<='Z')ad(ans,S[ch[i]-'A'+1][0][pos]),pos=nxt[ch[i]-'A'+1][0][pos],nt=i+1;else{nt=i+1;while(ch[nt]!=']')nt++;int u=0,pa=ch[nt-1]-'A'+1;for(int j=i+1;j<nt-1;j++)u=u*10+ch[j]-'0';for(int j=30;j>=0;j--)if(bin[j]<=u)ad(ans,S[pa][j][pos]),pos=nxt[pa][j][pos],u-=bin[j];nt++;}}printf("%d\n",ans);return 0;
}

这篇关于[bzoj5000][乱搞]OI树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---