#P4597. [Shoi2016]随机序列
[Shoi2016]随机序列
[SHOI2016] 随机序列
题目描述
给定一列数 。在每对相邻的数之间各插入一个加号、减号或乘号,共可得到 个表达式。按通常的运算优先级计算每个表达式的值,即先算乘法,再按从左到右的顺序加减。
每次操作把某个 改为 ,并询问此时所有表达式的值之和。修改永久生效,之后的操作以当前序列为基础。
输入格式
第一行两个正整数 ,分别为序列长度和修改次数。
第二行 个整数 。接下来 行各有两个整数 ,表示将 修改为 。
输出格式
输出 行。对于每个修改输出一行,包含一个整数,表示修改之后所有可能表达式的和,对 取模。
5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60
890543652
252923708
942282590
228728040
608998099
数据范围
所有数据满足 ,,。
- 对于 的数据,。
- 对于 的数据,。