最古遗迹（贡献延迟）

___Dice___ · 2025-11-20 09:28:21 · 个人记录

最古遗迹

考虑设 f_{i,j} 表示倒着考虑到 i，\leq j 的数都填了，剩下的所有数字都 >j+1，只考虑 \leq j 的数字的贡献。

考虑 f_{i,j} 去更新 i-1 的填的什么。

p为必须死的人数，q为必须活的人数

• i-1$ 必须死，那有 $f_{i,j} \times (j-p) \to f_{i-1,j}

1. 若 i-1 填 >j+1，f_{i,j} \to f_{i-1,j}（忽略 i-1 的贡献）。
2. 否则 i-1 填 =j+1。

设 j' 为填了 j+1 之后的到达的值。

可以算出来贡献是有多余的名额是 2\times (j'-j)，i-1 之后要用的名额是 j'-j-1，所以还剩下 2j'-2j-j'+j+1=j'-j+1 个。

接下来考虑剩下的 j+1,j+2...,j' 这其中每个数字都有 2 个，但是我之从其中选出来 n-(i-2) 个。