[洛谷P4491][HAOI2018]染色

我真的菜,这道题就是一个特别水的容斥,但是我一开始的时候在容斥的时候没有乘组合数,然后我GG了,这说明我对容斥不是很理解。
这个很容易想到一个$O(n^2)$的DP,但是过不了,所以很容易想到可以容斥。
令$f(i)$为前i种颜色出现S次,后面随便放的方案数,这个$f(i)$直接随便用组合数算一下就好了。
然后容斥一下求出$g(i)$(g(i)表示恰好i种颜色出现S次的方案数),这里要注意要乘一个组合数。然后这个式子可以NTT,然后就做完了。

Tagged with:

发表评论