轮廓线 dp 学习笔记
轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手：求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了，但是如果 $n = 10^5$ ，我们就要考虑使用轮廓线 dp 了。 设 $f_{i,S}$ 表示我们填到第 $i$ 行，我们在状压的状态中记录下图红线上...
轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手：求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了，但是如果 $n = 10^5$ ，我们就要考虑使用轮廓线 dp 了。 设 $f_{i,S}$ 表示我们填到第 $i$ 行，我们在状压的状态中记录下图红线上...
网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种，我们就需要用一种新的建图方法。 我们拿两道题目举例：RatingProgressAward*TCO2017 Semifinal 题目链接 如果对于积分做了前缀和之后我们发现题目就是要求在满足限制的条件下最大化区间和。 对于一个...
排版彻底崩了不管了 QAQ基础概念随机变量：有多种可能的取值的变量。$P(A)$：事件 $A$ 发生的概率。$E(X)$：随机变量 X 的期望值，$E(X) = \sum_{x} P(x=i)*i$独立事件：互相不影响的事件，满足 $P(AB) = P(A)P(B),E(AB) = E(A)E(B)$常用公式
题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目，我们有一种叫做 exlucas 的方法来算组合数（但是和 lucas 没有半毛钱关系）。 首先我们将模数 $m$ 质因数分解，最后用 CRT 合并一下就好了。 然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。 这样还是不能直接去乘逆元的，因为分母可能有因子 $p$，直接求逆元会变成 $0$ ...
记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑<h3>整除与不定方程</h3> $d|a,d|b \Leftrightarrow d|(a-b)$ 证明：$a = pd,b = qd,a-b = (p-q)d$$(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。证明：从右往左推：令 $g=(a,b)$,则有 $...