[扩展Min-Max容斥+DP]洛谷4707【重返现世】题解
题目概述有 $n$ 种物品，每单位时间出现 $i$ 物品的概率为 $p_i$ ，求恰好出现 $K$ 个不同物品的期望时间。解题报告Min-Max容斥？但是出现 $K$ 个是什么鬼啊。这里要用到扩...
[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解
题目概述有 $n$ 个带权糖果和 $n$ 个带权药片，求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始想的是求出 $\ge K$ 的方案...
[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$ 很小，所以要想办法搞成只和 $...
