ZigZagK的博客
CodeChef March Challenge 2019 Division 2
像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。Chef and Number Game最优解只能是正负分两半。#include<cstdio> #i...
[分治NTT+拆系数FFT+复杂度分析]BZOJ5398【admirable】题解
题目概述有 $n$ 个点的树,现在要覆盖 $K$ 条简单路径,需要满足每条边只能被覆盖 $0,1,K$ 次,求方案数。解题报告这题有毒,CF原题模数是 $998244353$ ,这里强行改成了 ...
[复杂度分析]LOJ6043(雅礼集训 2017 Day7)【蛐蛐国的修墙方案】题解
题目概述给出一个 $n$ 的排列 $\{p_n\}$(满足 $i\not=p_i$ ),求一个括号序列满足:1.是合法的括号序列。2.对于所有左括号 $i$ ,向 $p_i$ 连双向边,最后得到...
[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
题目概述原来有 $n​$ 个点的一棵树,现在加进了 $K​$ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七,不过这个解法能艹标程(度教rank1,翰...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)​$ 做法,但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题,我们可以把每项工作 $K_i$ 看成 $K_i$...
[除法分块+杜教筛]HHHOJ173【B】题解
解题报告重新看一遍发现这题十分斯波……我们要求的是:$$ \sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\ \sum_{\{a_k\}}\sum_{d|(a_1,a...
[STL乱搞+压位]BZOJ5087【Polycomp】题解
题目概述给出 $f(x),g(x),h(x)$ ,求 $f(g(x))\ mod\ h(x)$ ,系数在 $mod\ 2$ 意义下。解题报告直接就有一个 $O(n^2log_2n)$ 的多项式取...
[IDDFS]HHHOJ110【布加勒斯特的人偶师/Bucureşti】题解
解题报告考虑决策树,每次枚举操作,根据返回的结果把符合当前状态的排列分成三份(当然如果符合当前状态的只有 $1$ 个排列就不需要继续分了),我们要做的是把决策树的深度弄小。没错这就是个IDDFS...
[三元环计数]HDU6184【Counting Stars】题解
题目概述给出一张无向图,求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑,如果我们知道每条边所在的三元环个数 $num_i$ ,那么 $\sum_{i=1}^{m}{num_i...
[莫比乌斯函数+线性筛+离线+除法分块+调和级数]BZOJ3529(Sdoi2014)【数表】题解
题目概述有一张 $n\times m$ 的数表,其第 $i$ 行第 $j$ 列的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ , 计算数表中不大于 $a$ 的数之和。解题...