[非互质CRT]LOJ2721(NOI2018)【屠龙勇士】题解
题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT，根据同余方程的同除性，我们可以同除 $r=(atk_i,m_...
[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解
题目概述两个数 $x,y$ 可以匹配定义为 $x+y\ge H$ 。现在给出 $\{a_n\}$ 和 $\{b_m\}$ ，问 $\{a_n\}$ 有多少个连续子序列满足：存在一种方法...
[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解
题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le R\}$ 。给出 $m$ 个询问 ...
[裴蜀定理+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$），将他们加起...
[区间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$ 张打出，求所有方案造成的伤害之...
