P10956 金字塔题目描述虽然探索金字塔是极其老套的剧情但是有一队探险家还是到了某金字塔脚下。经过多年的研究科学家对这座金字塔的内部结构已经有所了解。首先金字塔由若干房间组成房间之间连有通道。如果把房间看作节点通道看作边的话整个金字塔呈现一个有根树结构节点的子树之间有序金字塔有唯一的一个入口通向树根。并且每个房间的墙壁都涂有若干种颜色的一种。探险队员打算进一步了解金字塔的结构为此他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔之后对金字塔进行深度优先遍历。机器人每进入一个房间无论是第一次进入还是返回都会记录这个房间的颜色。最后机器人会从入口退出金字塔。显然机器人会访问每个房间至少一次并且穿越每条通道恰好两次两个方向各一次 然后机器人会得到一个颜色序列。但是探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算对于一个给定的颜色序列有多少种可能的结构会得到这个序列。因为结果可能会非常大你只需要输出答案对10910^9109取模之后的值。输入格式输入仅一行包含一个字符串SSS长度不超过300300300表示机器人得到的颜色序列。输出格式输出一个整数表示答案。输入输出样例 #1输入 #1ABABABA输出 #15C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;string a;intdp[305][305];constintmod1e9;signedmain(){cina;intna.size();a a;for(inti1;in;i){dp[i][i]1;}for(intlen2;lenn;len){for(inti1;ilen-1n;i){intjilen-1;if(a[i]a[j]){for(intki1;kj;k){if(a[k]a[i]){dp[i][j]dp[i][k]*dp[k1][j-1];dp[i][j]%mod;}}dp[i][j]dp[i1][j-1];dp[i][j]%mod;}}}coutdp[1][n]\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容