看这篇题解
能学到挺多东西的。
首先是容斥原理，我们看到了序列题不超过一半，可以往这上面想，因为一定不会有两种元素同时超过一半
然后就是DP，我们在这种情况下的DP一般都是预处理，但是这道题目是每次都要枚举不合法的列\(col\)进行DP，所以思维不要被限制了
最后是DP的优化。这是我第一次见到通过观察最后的求式来优化DP的。观察最后的和式，我们发现我们只关心\(j>k\)的情况，所以可以将维度压缩成一维
标签：题解,最后,今天,Emiya,优化,我们,DP From： https://www.cnblogs.com/dingxingdi/p/18074292