#PQJ872x3280. QOJ 872_3280

    ID: 3052 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2021动态规划

QOJ 872_3280

标题: 随机数据 - Problem - QOJ.ac

#3280. 随机数据

Statistics

The problem was used in the following contests:

有 n 件物品,用 0,⋯,n−1 对它们编号,规定物品 i 的价值为 vi。

A 和 B 正在轮流玩一个游戏,该游戏会进行多轮。

每轮开始时,如果所有可用的物品都已经被取走,游戏将立刻结束。否则,A 必须选择一件未被取走的物品,将其取走。

假设 A 取走的物品编号为 i。接下来,B 可以选择从物品 (i−d+n)modn 和物品 (i+d)modn 中选取一件未被取走的物品,将其取走;或者他可以选择跳过本次操作。随后游戏进入到下一轮。特别地,如果这两件物品都已经被取走了,B 只能选择跳过本次操作。

A 和 B 都想最大化自己取走的物品的价值之和,我们假定 A 与 B 都采取了最优策略。

此外,在游戏开始前,有一些物品可能是不可用的。在游戏过程中,不可用的物品将会被忽略,即:A 和 B 都不能取走不可用的物品;当所有可用的物品都已经被取走时,游戏立刻结束。

初始时,所有物品都是可用的。你的程序需要支持 q 次操作,每次操作的内容为:给定一个 x,如果物品 x 是不可用的,它将变为可用的;如果它是可用的,它将变为不可用的。每次操作后,你需要回答:假设从当前状态开始游戏,游戏结束时 B 取走的物品的价值之和。

不幸的是,这是一道 IO 题,物品的数量可能会达到 1016。身为一个 OIer,你无法处理如此大规模的数据,因此 vi 将会用一种特殊的方法生成:给定一个长度为 m 的数组 w,vi=wimodm。

输入格式

从标准输入读入数据。

输入的第一行包含四个正整数 n,d,m,q,保证 1<n≤1016,1≤d<n,1≤m≤2×104,q≤105。

输入的第二行包含 m 个整数,第 i 个整数表示 wi−1 的值,保证 1≤wi≤400。

接下来的 q 行,每行包含一个整数 x,表示一次对物品 x 的操作。保证 0≤x<n。

输出格式

输出到标准输出。

输出 q 行,每行一个整数,对应一次操作之后的答案。

样例数据

样例 1 输入

5 2 3 2
1 3 2
1
1

样例 1 输出

3
4

样例 1 解释

在这组样例中,v0=1,v1=3,v2=2,v3=1,v4=3。

在第一次操作后,物品 1 处于不可用状态。双方都采取最优策略进行游戏,最终 B 取走的物品价值之和为 3。

在第二次操作后,所有物品都处于可用状态。双方都采取最优策略进行游戏,最终 B 取走的物品价值之和为 4。

样例 2 输入

10 4 5 5
40 355 190 215 161
3
4
0
3
4

样例 2 输出

581
460
420
541
702

样例 3

见下发文件。

数据范围与提示

Subtask 1 (5 pts) : n≤20,q=1

Subtask 2 (10 pts) : n≤105,q=1

Subtask 3 (15 pts) : n,q≤105

Subtask 4 (30 pts) : q=1

Subtask 5 (40 pts) : 无特殊限制。

如有需要,可以使用 __int128 处理 long long 乘法取模,下面是一个使用 __int128 计算 a×bmodm 的例子:

long long a = 1e15;
long long b = 1e15;
long long m = 12345678910;
long long c = ((__int128) a * b) % m;