misc

\[ v_p(n!)=\sum_{k\ge1}\lfloor\frac{n}{p^k}\rfloor=\frac{n-\mathrm{sum\_of\_digits}(n)}{p-1} \]

thus

\[ v_p(\binom {n+m}m) = \#\text{lifting in p-ary addition n + m.} \] 3

上下都有限制的折线法: 可以反复映射,做到\(O(n+m/(a+b))\)的复杂度.2

切比雪夫距离与曼哈顿距离转化

区间DP套数位DP, WTF? 数位DP, 但上下界不独立: 记录0/1/2表示顶上界/下界/自由选择

多想想极限情况,最后再想推广