[Min-Max容斥+树上解方程]LOJ2542(PKUWC2018)【随机游走】题解
题目概述有一棵树，刚开始你在 $X$ ，每次随机走到相邻的点。有 $q$ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。解题报告不难想到Min-Max容斥，令 $min(S)...
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造，导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
PKUWC2019没约记
Day [-n,-2]填了一堆算法坑（然后都没有用到）。Day -1从13:00跑图到22:00。Day 0下午报到，试机的时候发现是Win7，里面真的是应有尽有……Sublime,Emacs,...
[BSGS+矩阵求逆]BZOJ4128【Matrix】题解
题目概述给出矩阵 $A,B$ ，求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ，上BSGS！枚举 $A^{im}A...
[三元环计数]HDU6184【Counting Stars】题解
题目概述给出一张无向图，求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑，如果我们知道每条边所在的三元环个数 $num_i$ ，那么 $\sum_{i=1}^{m}{num_i...
[伯努利数+拆系数FFT+多项式求逆]51Nod1258【序列求和 V4】题解
题目概述求 $\sum_{i=1}^{n}i^K,K\le 50000$ 。解题报告同51Nod1228，只不过 $K\le 50000$ 所以不能 $O(K^2)$ 处理伯努利数，于是我们根据...
[伯努利数]51Nod1228【序列求和】题解
题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着，但是 $n$ 太tm大了，不过 $K$ 很小，所以要想办法搞成只和 $...
[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$ 的期望时间。解...
