menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[指数型生成函数+多项式ln]BZOJ3456【城市规划】题解
题目概述求 $n$ 个点简单无向连通图的个数。解题报告我感觉好像重新学了一遍指数型生成函数的样子……普通型生成函数解决的是组合问题,而指数型生成函数解决的是排列问题,比如把 $n​$ 个不同的物...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[插头DP]BZOJ2331(SCOI2011)【地板】题解
题目概述有 $n\times m$ 的客厅,要用 $L$ 型地板覆盖整个客厅,求方案数。解题报告棋盘覆盖问题,$min\{n,m\}\le 10$ ,想到插头DP,由于每个 $L$ 型地板只有一...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[插头DP]BZOJ1814(Ural 1519)【Formula 1】题解
题目概述给出 $n\times m$ 的网格图,其中有些格子是障碍,求有多少种方法用一条哈密顿回路覆盖没有障碍的格子。解题报告ps:大量图片来自于cdq的课件QAQ。这道题的退化版是HDU169...
apps DP,BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解
题目概述有 $n$ 个带权糖果和 $n$ 个带权药片,求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始想的是求出 $\ge K$ 的方案...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合,求选出若干个子集(不可以不选)相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造,导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着,鸽了。解题报告用Min-Max容斥再做一遍这题,学习自memset0。Min-Max容斥,对于一个集合 $S$ ,他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
[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 条评论
阅读全文
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ,每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数,生成 $i$ 的概率为 $p_i$ ,问 $x$ 变成 $2^n-1$ 的期望时间。解...
local_offer 查看标签
comment 0 条评论
阅读全文
[矩阵树定理]BZOJ4894【天赋】题解
题目概述有 $n$ 个技能,每个技能有一些前置技能,现在 $1$ 技能已学习,求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数:外向树:边从父亲到儿子的有向树度数矩阵为每...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[莫比乌斯函数+线性筛]BZOJ3309【DZY Loves Math】题解
题目概述令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂,$m$ 次询问,每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]$ 。解题报告先正常操作一下:...
keyboard_arrow_up