[FMT]WC2018【州区划分】题解
解题报告搜FMT搜到这道题，其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积，他是这样的：$$
h_s=\sum_{A\subset...
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变成 $2^n-1$ 的期望时间。解...
[cdq分治+NTT]洛谷4721【分治 FFT】题解
题目概述给出 $g$ 以及 $f(0)=1$ ，求：$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的，结果搜分治FFT就搜到这个了，于是填...
[贪心]NOIP2018Day2【旅行】题解
解题报告树的情况直接贪心做，基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅，少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版，大佬们可以去切啊QAQ。示例程序#include&...
[矩阵树定理]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$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题，问题是行列式取模，因为不是质数所以不能逆元。那么辗转相除就...
[矩阵树定理]SPOJ(HIGH)【Highways】题解
题目概述给出一张无向图，求生成树个数。解题报告大佬传送门：*ZJ，Candy?。矩阵树定理裸题，先来讲（瞎扯）一波行列式：行列式定义式：$Det(A)=\sum_{P}(-1)^{\tau(P)...
[原根+NTT+快速幂]BZOJ3992(SDOI2015)【序列统计】题解
题目概述有 $S$ 个数，取 $n$ 次（可重复取），将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成NTT就行了。我原来以为这道题是循环...
