[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解
题目概述有 $n$ 个带权糖果和 $n$ 个带权药片，求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始想的是求出 $\ge K$ 的方案...
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造，导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
[BSGS+矩阵求逆]BZOJ4128【Matrix】题解
题目概述给出矩阵 $A,B$ ，求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ，上BSGS！枚举 $A^{im}A...
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变成 $2^n-1$ 的期望时间。解...
[矩阵树定理]BZOJ4894【天赋】题解
题目概述有 $n$ 个技能，每个技能有一些前置技能，现在 $1$ 技能已学习，求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数：外向树：边从父亲到儿子的有向树度数矩阵为每...
[莫比乌斯函数+线性筛]BZOJ3309【DZY Loves Math】题解
题目概述令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂，$m$ 次询问，每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]$ 。解题报告先正常操作一下：...
[矩阵树定理]BZOJ4766【文艺计算姬】题解
题目概述求二分图 $K_{n,m}$ 的生成树个数。解题报告我骗我自己：$A+B=d(dA+dB)$ ，导致我做不出来。二分图的基尔霍夫矩阵的一个主子式长这样（上面 $n$ 行，下面 $m-1$...
[矩阵树定理]BZOJ4031(HEOI2015)【小Z的房间】题解
题目概述有 $n\times m$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题，问题是行列式取模，因为不是质数所以不能逆元。那么辗转相除就...
[原根+NTT+快速幂]BZOJ3992(SDOI2015)【序列统计】题解
题目概述有 $S$ 个数，取 $n$ 次（可重复取），将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成NTT就行了。我原来以为这道题是循环...
