xiezheyuan
-
中国剩余定理（CRT）学习笔记
约定 \(A\perp B\) 表示 \(\gcd(A,B)=1\)。 \(A\mid B\) 表示 \(B\equiv 0\pmod{A}(A\neq0)\)。 引入 考虑以下这道题： 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。 問物幾何？—— 《孫子算經》 也就是说，求出下列关于 \(x\) 方程组的最小整数解： \[\begin{case…
-
四边形不等式学习笔记
简要题意 四边形不等式是一种 dp 优化策略。多用于 2D DP。 内容 对于区间 \([l,r]\) 带来的贡献 \(w(l,r)\)，如果其满足： 对于 \(L\leq l\leq r \leq R\)，\(w(L,r)+w(l,R)\leq w(L,R)+w(l,r)\) 则称 \(w\) 满足四边形不等式。特别地，如果上式符号取等，则称其满足四边形恒…
