AGC012D Colorful Balls

题意： 个球排成一排，第 个球有颜色 和重量 。

可以执行下列两种操作：

• 选择两个颜色相同，且重量之和不超过 的球，交换他们的位置。

• 选择两个颜色不同，且重量之和不超过 的球，交换他们的位置。

求可以得到多少种不同的颜色序列。答案对 取模。

，，时限 。

---

对于两个能够交换的球，连一条无向边。

对于一个联通块内的球，可以随便交换顺序，最终方案数即为颜色的多重排列。

这能得到一个显然的 做法。

考虑简化连边。

考虑最终形成联通块的形态，不难发现是一个大多色块和若干（没有贡献）的单色块。

（若有两个多色块，则必然能合成一个）

大多色块是由若干颜色的（按重量排序的）前缀组成的。

于是，最轻的球一定在大多色块中。

对于同色的球，只需要考虑最轻的球连出的边。

对于异色球，只需要考虑全局最轻的球连出的边，以及全局最轻球所在颜色能连出的最容易的边（即除掉这个颜色后的最轻球）。

这样，所需的边就是 的了。

适当地思考性质可以简化代码实现。