P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ 再限制列。 令 $g(i,j)$ 为只是用 $i$ 种颜色，只填 $j$ 列的方案数。 $$ f(i)=\sum\limits_{j=0}^m\dbinom{m}{j}(-1)^{c-j}g(i,j) $$ 最后 $$ g(i,j)=((i+1)^j-1)^n $$ 带入求解即可，时间复杂度 $O(mc\log n)$ 。 Code #include<bits/stdc++.h> #defi..
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=n+1$ )。 那么易证，这个左括号对所有 $i\le r＜ j$ 且 $1\le l\le i$ 的区间都有 1 的贡献，总贡献即为 $i\times(j-i)$ 。 右括号同理，因此可以 $O(n)$ 计算。 $K>1$ 套用 $K=1$ 时的计算方法，找贡献。 我们发现对于一个 $K$ 级偏值的字符串，只会对包含它的母串的 $K+1$ 级偏值造成贡献。 还是假设以下一个下标为 $i$ 的左括号，..
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为 queryrk() 找的是小于 k 的数，而 check 的要求是小于等于 k 的数。 Code #include<bits/stdc++.h> #define N 100005 #define orz puts("orzwyy332623");//tiaoshi #define ls(p) p<<1 #define rs(p) p<<1|1 using ..
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$ 即为 $n$ 次单位根。(有 $n$ 个) 本原单位根：$e^{i\frac{2\pi}{n}}$ 称为 $n$ 次单位根的本原单位根，记为 $ω_n$ 。 原根：若 $1\le g\le n-1$ 且 $g$ 模 $n$ 的阶为 $\varphi(n)$ ，则称 $g$ 为 $n$ 的原根。 卷积的一般形式： $$ c_i=\sum\limits_{i=j\oplus k}a_jb_k $$ DFT ..