[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就行了。我原来以为这道题是循环...
[思维+背包]BZOJ5003【与链】题解
题目概述有权值为 $0\sim n$ 的 $n+1$ 个点，如果 $u\ and\ v=v$ 那么 $u$ 有一条到 $v$ 的有向边，现在问点数为 $k$ ，且权值加和为 $n$ 的路径条数（...
[点分树]BZOJ1095(ZJOI2007)【Hide 捉迷藏】题解
题目概述有一棵黑白两种颜色的树，两种操作：1.修改一个节点的颜色。2.询问最远的黑点之间的距离。解题报告如果没有修改的话就是裸的点分治，但是有修改的话就凉了……这里要用到点分树，可以实现动态点分...
