![P6076 [JSOI2015]染色问题 题解](/images/covers/1.jpg)
P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ …
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=…
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为…
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$…