menu ZigZagK的博客
account_circle

正在努力加载中QAQ

Min_25筛
一类问题已知积性函数 $f(n)$ ,其中 $f(p)$ 是简单多项式,且 $f(p^k)$ 可以快速计算( $p$ 是素数),求其前缀和。上杜教筛?如果 $f(n)​$ 很奇怪就没法卷另外一个...
local_offer 查看标签
comment 0 条评论
阅读全文
[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
题目概述在 $n\times m$ 的网格上有 $k$ 个景点,选取每个网格都有代价,求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示...
apps BZOJ,DP
local_offer 查看标签
comment 2 条评论
阅读全文
[插头DP]BZOJ1814(Ural 1519)【Formula 1】题解
题目概述给出 $n\times m$ 的网格图,其中有些格子是障碍,求有多少种方法用一条哈密顿回路覆盖没有障碍的格子。解题报告ps:大量图片来自于cdq的课件QAQ。这道题的退化版是HDU169...
apps BZOJ,DP
local_offer 查看标签
comment 0 条评论
阅读全文
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合,求选出若干个子集(不可以不选)相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造,导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着,鸽了。解题报告用Min-Max容斥再做一遍这题,学习自memset0。Min-Max容斥,对于一个集合 $S$ ,他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
[伯努利数]51Nod1228【序列求和】题解
题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着,但是 $n$ 太tm大了,不过 $K$ 很小,所以要想办法搞成只和 $...
local_offer 查看标签
comment 0 条评论
阅读全文
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ,每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数,生成 $i$ 的概率为 $p_i$ ,问 $x$ 变成 $2^n-1$ 的期望时间。解...
local_offer 查看标签
comment 0 条评论
阅读全文
[矩阵树定理]SPOJ(HIGH)【Highways】题解
题目概述给出一张无向图,求生成树个数。解题报告大佬传送门:*ZJ,Candy?。矩阵树定理裸题,先来讲(瞎扯)一波行列式:行列式定义式:$Det(A)=\sum_{P}(-1)^{\tau(P)...
apps 图论,SPOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[Miller-Rabin+Pollard-Rho]Codeforces1025B【Weakened Common Divisor】题解
题目概述有 $n$ 组数对 $(a_i,b_i)$ ,求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。解题报告因为随便求所以找共有的素因子就好了,那么先求出 $GCD$ ...
[DFS序上DP]一种带依赖的树上背包
题目概述BZOJ4182弱化版,原版是要求选出来的点是连通的(我不会),弱化版只需要满足儿子选了父亲必选。解题报告其实之前做过带依赖的一道题,但是并没有体积,所以依然可以用正常的树形DP做。但这...
apps DP
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up