ZigZagK的博客
[矩阵乘法]BZOJ4417(Shoi2013)【超级跳马】题解
题目概述现有一个 $n$ 行 $m$ 列的棋盘,一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列,且跳到本行或相邻行。跳越期间,马不能离开棋盘。试求跳法种数 $mod\ 30011$ 。解...
[主席树+平衡树]BZOJ4548【小奇的糖果】题解
题目概述有 $n$ 个有颜色的点,颜色有 $K$ 种,现在选一条线段并获取上面或下面的所有点,规定获得的点不能包含所有颜色,问你能获得多少点。解题报告我怎么套路题都不会做啊……首先有显然的贪心,...
[裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解
题目概述给你 $n$ 种物品,每种物品有无数个,体积为 $V_i$ ,选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ,问方案数。解题报告怎么我一道HAOI题都不会啊...
[SG函数]LOJ2126(HAOI2015)【数组游戏】题解
题目概述有一个长度为 $n$ 的数组,甲乙两人在上面进行这样一个游戏:首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子,假设它的下标为 $x$ 。接着...
[矩阵快速幂]LOJ2128(HAOI2015)【数字串拆分】题解
题目概述你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数,你可以将这个数字串分割成若干个数字(允许前导 $0$),将他们加起...
[拆系数FFT]洛谷4245【任意模数NTT】题解
题目概述求 $A(x)B(x)$ ,系数对任意模数 $p$ 取模。解题报告任意模数NTT好像需要三模数NTT搞。然而我不会NTT……所以我来愉快的讲一波任意模数FFT(雾)。其实洛谷里panda...
[区间DP]LOJ2063(HAOI2016)【字符合并】题解
题目概述有一个长度为 $n​$ 的 $01​$ 串,你可以每次将相邻的 $k​$ 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k​$ 个字符确定。你需要求出你能获得的最...
[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解
题目概述我们知道,求任意图的最大独立集是一类NP完全问题,目前还没有准确的多项式算法,但是有许多多项式复杂度的近似算法。例如,小C常用的一种算法是:对于一个 $n$ 个点的无向图,先等概率随机一...
[后缀数组+线段树]LOJ2064(HAOI2016)【找相同字符】题解
题目概述给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波:把两个串接在一起(加个分隔符),求后缀数组...
[DP+组合]LOJ2538(PKUWC 2018)【Slay the Spire】题解
题目概述有 $n$ 张攻击牌(造成攻击牌数值的伤害)和 $n$ 张强化牌(攻击牌伤害均 $\times$ 强化牌数值),从中抽出 $m$ 张并选出最优秀的 $K$ 张打出,求所有方案造成的伤害之...