menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[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,...
apps 游记
local_offer 查看标签
comment 1 条评论
阅读全文
[BSGS+矩阵求逆]BZOJ4128【Matrix】题解
题目概述给出矩阵 $A,B$ ,求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ,上BSGS!枚举 $A^{im}A...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[三元环计数]HDU6184【Counting Stars】题解
题目概述给出一张无向图,求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑,如果我们知道每条边所在的三元环个数 $num_i$ ,那么 $\sum_{i=1}^{m}{num_i...
apps HDU
local_offer 查看标签
comment 0 条评论
阅读全文
[伯努利数+拆系数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$ 很小,所以要想办法搞成只和 $...
local_offer 查看标签
comment 0 条评论
阅读全文
[FMT]WC2018【州区划分】题解
解题报告搜FMT搜到这道题,其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积,他是这样的:$$ h_s=\sum_{A\subset...
apps 洛谷
local_offer 查看标签
comment 0 条评论
阅读全文
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ,每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数,生成 $i$ 的概率为 $p_i$ ,问 $x$ 变成 $2^n-1$ 的期望时间。解...
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up