← 返回题目列表

AtCoder · arc218_f

F. 桶

中文机器翻译题面 查看原题

分数: 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