分数: 700 点
问题陈述
问题F和F2是相同的问题,但约束条件不同 M。在问题F中, 1 \le M \le 4.
给你一个正整数 M。考虑以下问题。
桶给你一个正整数 N 和非负整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N) 长度 N。的所有元素 A 和 B 之间 0 和 M,包括在内。
有 N 桶已编号 1 to N。每个桶最多可容纳 M 升水。最初,桶 i 包含 A_i 升水。
您可以多次执行以下操作。
- 选择两个不同的桶 i 和 j。继续从桶里倒水 i 放入桶中 j 只要满足以下两个条件:
- 桶 i 仍有剩余水。
- 桶中的水量 j 小于 M 升。
你的目标是准确地 B_i 桶中的水升数 i 对于所有人 i。确定目标能否实现。
给定一个非负整数矩阵 X=(X_{i,j})(0 \le i,j \le M) of (M+1) 行和 (M+1) 列。处理以下查询 Q 次。
- 给你非负整数 i,j,Y 与 0 \le i,j \le M。改变 X_{i,j} to Y。然后,获取非负整数序列 A 和 B 通过以下步骤。
- 初始化非负整数序列 A 和 B 作为空序列。
- 对于 i = 0,1,\dots,M 按此顺序:
- 对于 j = 0,1,\dots,M 按此顺序:
- 这样做 X_{i,j} 次:追加 i 到年底 A 和 j 到年底 B.
- 解决 桶 对于非负整数序列 A 和 B 长度 N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}.
约束
- 1 \le M \le 4
- 1 \le Q \le 10^6
- 0 \le X_{i,j},Y \le 10^{17}
- 0 \le i,j \le M
- \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1 随时。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
M Q
X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}
X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}
\vdots
X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
i\ j\ Y
输出
输出 Q 行。的 i- 第行应包含 Yes 如果目标能够在 \mathrm{query}_i,和 No 否则。
示例输入 1
3 3 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 2 3 1 2 1 1
示例输出 1
Yes No Yes
第一个查询使 X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} ,我们得到 A=(1,1,2),B=(2,2,0).
在这种情况下,例如可以通过以下操作序列来实现该目标。
- 设置 i = 1,j = 2。每个桶中的水量变化为 (1,1,2) to (0,2,2).
- 设置 i = 3,j = 1。每个桶中的水量变化为 (0,2,2) to (2,2,0).
第二个查询使得 X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} ,我们得到 A=(1,1,2,2),B=(2,2,0,3).
这种情况下,无论怎么操作都无法达到目的。
第三个查询使得 X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} ,我们得到 A=(1,1,2,2,2),B=(2,2,0,1,3).
在这种情况下,例如可以通过以下操作序列来实现该目标。
- 设置 i = 1,j = 2。每个桶中的水量变化为 (1,1,2,2,2) to (0,2,2,2,2).
- 设置 i = 3,j = 1。每个桶中的水量变化为 (0,2,2,2,2) to (2,2,0,2,2).
- 设置 i = 4,j = 5。每个桶中的水量变化为 (2,2,0,2,2) to (2,2,0,1,3).
示例输入 2
4 10 45636788580181785 16131322312654301 43477244591521823 6505049084010674 86530627327096446 95921187347997793 55491565467039163 87684565747362311 80318628430974482 12308092878301956 75570615154690027 96403707363045776 14150012766408204 6612197700307407 64417022692908525 5530468643826479 41731276604630756 15675296751519388 59461896803210859 66666666666666666 72767956047192820 18258893791516726 58852629621892634 33333333333333333 29923985408775019 2 1 26541245644686826 2 4 29485791833729050 4 1 21832826336874318 3 2 4953499115446612 2 0 69217973349997921 2 4 23133150029036944 3 4 55834224798559242 1 2 98517007615469735 2 3 3768060024403703 0 4 87241661746072372
示例输出 2
No Yes No Yes No Yes No No No No