#P7206. [2018西部多校]Sequence

    ID: 7007 传统题 2000ms 888MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DP计数 DP转移矩阵转移矩阵乘积矩阵求逆差分转化

[2018西部多校]Sequence

题目描述

给定一个只含大小写英文字母的字符串 SS,令 n=∣S∣n=|S|。对区间 [l,r][l,r],记 cnt⁡l,r\operatorname{cnt}_{l,r} 为子串 S[l,r]S[l,r] 的本质不同子序列数。大小写字母不同,空串也计入。

共有 QQ 次询问,使用前一次答案生成下一次区间。记 X=998244353X=998244353,给定初始值 a0,b0a_0,b_0 和参数 p,q,rp,q,r,令 z0=0z_0=0。对于 i=1,…,Qi=1,\ldots,Q,依次计算

$$\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}$$

只需输出最后一次询问的 zQz_Q。

输入格式

第一行一个字符串 SS。第二行六个整数 Q,a0,b0,p,q,rQ,a_0,b_0,p,q,r。

输出格式

一行一个整数,表示 zQz_Q。

样例

ababA
2 4 6 8 10 12
7

数据范围与约定

数据比例 n,Qn,Q 的上界
20% 10310^3
40% 10410^4
60% 10510^5
100% 10610^6

对于全部数据,1≤n,Q≤1061\le n,Q\le 10^6,0≤a0,b0,p,q,r<X0\le a_0,b_0,p,q,r<X。原稿的询问递推未单独列出 z0z_0,站内按 z0=0z_0=0 生成询问。

原 PDF 题面