简单算法题

题目信息

时间限制: 1s

空间限制: 256M

输入文件: algorithm.in

输出文件: algorithm.out

题目描述

基于括号序列可以出许多有趣的简单算法题，一个合法括号序列的定义如下：

() 是合法的。
如果括号序列 X 是合法的，那么括号序列 (X) 是合法的。
如果括号序列 X 和 Y 都是合法的，那么括号序列 XY 是合法的

例如，括号序列 ()()(()) 是合法的，()))()(( 是不合法的。

定义一个生成括号序列的操作流程：

给定长度为 $n$ 的整数序列 $c_0, c_1, \ldots, c_{n-1}$ ，依次执行 $n$ 次操作构建括号序列。
初始时括号序列为空，第 $i+1$ 次操作时，若 $i$ 为偶数，则往当前括号序列末尾加人 $c_i$ 个左括号；否则就往当前括号序列末尾加 $c_i$ 个右括号。

例如，序列 3211 构建出来的括号序列为 ((())()。

注意，按照上述流程构建出来的括号序列 $\mathrm{S}$ 不一定是合法的，但是 $\mathrm{S}$ 的子串有可能是合法括号序列，请求出 $\mathrm{S}$ 的非空子串是合法括号序列的数量。

即求有多少个区间 $[l, r](1 \leq l \leq r \leq|S|)$ ，使得 $S[l, r]$ 是合法括号序列。

输入格式

本题采用如下方式生成输入数据：

输入仅一行，8 个整数 $n, x, y, z, m_0, m_1, c_0, c_1$ 。

对于 $i>1, c_i=\left(c_{i-1} \times x+c_{i-2} \times y+z\right) \bmod M_i+1$ ，其中当 $i$ 为偶数时 $M_i=m_0$ ，当 $i$ 时奇数时 $M_i=m_1$ 。

整数序列 $c$ 的含义如题所述。

输出格式

一行一个整数表示 $\mathrm{S}$ 中合法的非空括号子串的数量。

样例

样例输入 1

10 686962104 149902149 5232363 10 4 7 3

样例输出 1

数据范围

$\begin{aligned} & 1 \leq n \leq 10^7, 0 \leq x, y, z \leq 10^9, 1 \leq c_0 \leq m_0 \leq 10^9, 1 \leq c_1 \leq m_1 \leq 10^9 \\ & \text { subtask } 1(8 p t s): n \leq 20, \max \left\{m_0, m_1\right\} \leq 500 \\ & \operatorname{subtask} 2(16 p t s): n \leq 5000, \max \left\{m_0, m_1\right\} \leq 4000 \\ & \text { subtask } 3(8 p t s): n \leq 20 \\ & \text { subtask } 4(16 p t s): n \leq 5000 \\ & \text { subtask } 5(8 p t s): n \leq 10^6, m_1=1 \\ & \text { subtask } 6(28 p t s): n \leq 10^6 \\ & \text { subtask } 7(16 p t s): \text { 无限制 }\end{aligned}$