2022-2023:teams:loaf_on_contest:front_page:st3

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2022-2023:teams:loaf_on_contest:front_page:st3 [2022/08/31 22:47]
yuki
+++ 2022-2023:teams:loaf_on_contest:front_page:st3 [2022/08/31 22:58] (当前版本)
yuki
@@ 行 8: / 行 8: @@
 WA是因为思路不对。
 ====H====
+首先把 $a$ 数组排序，从小到大枚举 $a_i$。
+首先考虑 $a_{i-1} - a_i$ 的右部点，再考虑 $a_i$ 对应的左部点。
+需要统计的是 右 -> 左 -> 右 -> 左 ... -> 右 这样的链的数量为i时的情况数。
+对于右部点，只会将链的数量+1（单独一个 右 ） add(f[k], f[k - 1])
+对于 $a_i$ 对应的左部点 它和前面所有右部点都有连边，因此它可以把两个链连成一个
+即：add(f[j - 1], (j - 1ll) * j % mod * f[j] % mod)
+每次枚举到i，相当于是枚举到了环的最后一个点，需要将当前的f[1]累加进答案，因为当前 $a_i$ 对应的左部点，一定可以把 "右 -> 左 -> 右 -> 左 ... -> 右 " 这样一个链的第一个和最后一个 右部点连起来。
 ====F====

2022-2023/teams/loaf_on_contest/front_page/st3.1661957268.txt.gz · 最后更改: 2022/08/31 22:47 由 yuki