CF38H 题解

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)\) 但常数比较小的。