CF38H 题解

发布时间 2023-09-22 12:10:38作者: liangbowen

problem & blog

远古场翻到的一个不错的题,提供一个好想很多的做法。


求出任意两点的路径在全部路径中是第几个。然后随便找两个人,钦定他们是 Au 吊车尾与 Cu Rank1。这样子就可以直接求出全部人可以是否可以拿 Au Ag Cu 了。

然后就是傻子 DP 了,往状态里塞 Au 与 Ag 的人数,转移随便转移,方案数即 \(\sum\limits_{g1\le i\le g2, s1 \le j\le s2} dp_{n,i,j}\)。答案即全部方案数的和。

code,时间复杂度 \(O(n^5)\) 但常数比较小的。