#P17760. 机拳猜
机拳猜
题面描述
小 又双叒叕在 模拟赛得到“正确”的题意。
让我们来到事发现场:
给一个由 这三种字母组成的字符串 ,其中 分别表示石头,剪刀和布。我们要进行 轮运算。
每一轮,我们会将 中相邻两个字符进行进行比较,并且保留能够获胜的那个手势(如果平局,那么任意保留一个)。这样就能得到一个长度为 的字符串。
现在给定一个整数 和一个字符串 ,求以下问题的答案:
长度为 的剪刀石头布字符串共有 种可能性。在这些字符串中,有多少字符串经过 轮运算后,会输出字符串 ?
于是他根据他的理解出了一道新题。
题目描述
给一个由 这三种字母组成的字符串 ,其中 分别表示石头,剪刀和布。我们要进行 轮运算。
每一次,我们会将 中相邻两个字符进行进行比较,并且保留能够获胜的那个手势(如果平局,那么任意保留一个)。这样就能得到一个长度为 的字符串。
现在给定一个整数 和一个字符串 ,求以下问题的答案:
长度为 的剪刀石头布字符串共有 种可能性。在这些字符串中,有多少字符串经过 次比较后,可以得到字符串 ?
输出答案对 取模的结果。 不一定是质数。
,
相信大家都看出了两道题目的区别,原题每一轮同时将每一对相邻位置进行比较,每对的结果作为下一轮的字符串,而本题是任选一对比较,新串是在原串基础上删掉一个字符而得。
输入格式
第一行一个字符串 。
第二行两个数 。
输出格式
输出一个数表示答案。
样例输入 #1
RR
2 20
样例输出 #1
17
样例输入 #2
SSPPPSS
7 998244353
样例输出 #2
291335
数据范围
令 。
对于所有数据,,,。
部分分如下,表中未填表示没有特别的限制。
| 子任务 | 分值 | 特殊性质 | ||
|---|---|---|---|---|
| 1 | 5 | |||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | ||||
| 7 | ||||
| 8 | 为 的循环 | |||
| 9 | 10 | 只由 构成 | ||
| 10 | ||||
| 11 | ||||
| 12 | ||||
| 13 | ||||
| 14 | ||||