menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[矩阵树定理]BZOJ4766【文艺计算姬】题解
题目概述求二分图 $K_{n,m}$ 的生成树个数。解题报告我骗我自己:$A+B=d(dA+dB)$ ,导致我做不出来。二分图的基尔霍夫矩阵的一个主子式长这样(上面 $n$ 行,下面 $m-1$...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[矩阵树定理]BZOJ4031(HEOI2015)【小Z的房间】题解
题目概述有 $n\times m$ 的网格,每个网格是房间或者柱子,周围都有墙,问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题,问题是行列式取模,因为不是质数所以不能逆元。那么辗转相除就...
[原根+NTT+快速幂]BZOJ3992(SDOI2015)【序列统计】题解
题目概述有 $S$ 个数,取 $n$ 次(可重复取),将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成NTT就行了。我原来以为这道题是循环...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[思维+背包]BZOJ5003【与链】题解
题目概述有权值为 $0\sim n$ 的 $n+1$ 个点,如果 $u\ and\ v=v$ 那么 $u$ 有一条到 $v$ 的有向边,现在问点数为 $k$ ,且权值加和为 $n$ 的路径条数(...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[点分树]BZOJ1095(ZJOI2007)【Hide 捉迷藏】题解
题目概述有一棵黑白两种颜色的树,两种操作:1.修改一个节点的颜色。2.询问最远的黑点之间的距离。解题报告如果没有修改的话就是裸的点分治,但是有修改的话就凉了……这里要用到点分树,可以实现动态点分...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[第二类斯特林数+多项式求逆]BZOJ4555(Tjoi2016&Heoi2016)【求和】题解
题目概述求 $f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\cdot2^j\cdot j!$ ,$S(i,j)$ 表示第二类斯特林数。解题报告$S(i,j)$ ...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[莫比乌斯函数+线性筛+离线+除法分块+调和级数]BZOJ3529(Sdoi2014)【数表】题解
题目概述有一张 $n\times m$ 的数表,其第 $i$ 行第 $j$ 列的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ , 计算数表中不大于 $a$ 的数之和。解题...
[莫队+STL乱搞]BZOJ4810(Ynoi2017)【由乃的玉米田】题解
题目概述给出一个序列 $\{a_n\}$ 和 $m$ 次询问,每次询问 $[L,R]$ 中是否有两个数相加为 $x$ 或两个数相减为 $x$ 或两个数相乘为 $x$ 。解题报告看我都死了3个礼拜...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[启发式分裂]BZOJ4059(Cerc2012)【Non-boring sequences】题解
题目概述判断一个序列是否满足所有子序列都有一个数只出现了一次。解题报告可以用矩形覆盖+扫描线的方法,不过可以像NWERC2017F一样启发式分裂。一个数左边第一个相同的数和右边第一个相同的数这一...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[思维+FFT]BZOJ4259【残缺的字符串】题解
题目概述有两个串 $A,B$ ,有些位置是通配符,求 $A$ 可以在 $B$ 的哪些位置匹配。解题报告早就听说了这题,今天来填坑。判断两个字符串相等可以用式子:$\sum_{i=0}^{len}...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up