#P7206. [2018西部多校]Sequence
[2018西部多校]Sequence
题目描述
给定一个只含大小写英文字母的字符串 ,令 。对区间 ,记 为子串 的本质不同子序列数。大小写字母不同,空串也计入。
共有 次询问,使用前一次答案生成下一次区间。记 ,给定初始值 和参数 ,令 。对于 ,依次计算
$$\begin{aligned} a_i&=(p a_{i-1}+q b_{i-1}+z_{i-1}+r)\bmod X,\\ b_i&=(p b_{i-1}+q a_{i-1}+z_{i-1}+r)\bmod X,\\ x_i&=\min(a_i\bmod n,b_i\bmod n)+1,\\ y_i&=\max(a_i\bmod n,b_i\bmod n)+1,\\ z_i&=\operatorname{cnt}_{x_i,y_i}\bmod X. \end{aligned}$$只需输出最后一次询问的 。
输入格式
第一行一个字符串 。第二行六个整数 。
输出格式
一行一个整数,表示 。
样例
ababA
2 4 6 8 10 12
7
数据范围与约定
| 数据比例 | 的上界 |
|---|---|
| 20% | |
| 40% | |
| 60% | |
| 100% |
对于全部数据,,。原稿的询问递推未单独列出 ,站内按 生成询问。