本文摘自 cancan123456 的《卡哈希》。 本文基于 NOI WC 2024 csy 专家进行的讲解。 什么？你还在为卡不掉选手的十模哈希而感到痛苦？ 什么？你还在 CF hack 时看着对方的随机五十模数哈希而感到迷茫？ 不要担心，现...

Floyd 求最短路，时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。 123for (int k = 1;k <= n;++k) for (int i = 1;i <= n;++i) for (int ...

Weighted Tic-Tac-Toe 用二进制表示每一格的情况，然后必胜态和必败态需要相互转换。 Remove Pairs 直接状压，时间复杂度 $O(2^nn^2)$。 Exchange Game $dp_{f,st}$ 表示某一方...

定义：一棵有根树形成的任一排列 $p$，若 $i$ 是 $j$ 的父亲，排列 $p$ 均满足 $i$ 在 $j$ 之前。更加形式化的，$\forall 1 \le i < j \le n$，$p_j$ 均不是 $p_i$ 的父亲。 结论：设...

母题—逆序对与期望 求长度为 $n$ 的排列的期望的逆序对个数。 对于每一对数，是否成为逆序对的概率显然为 $\frac{1}{2}$，那么就有： E(x) = E(\sum\limits_{i,j\mid i < j}[a_i > a_j])...

$\gcd (x,y)$ 求两个数 $x,y(x > y)$ 的最大公因数，辗转相除法即可。 1int gcd (int x,int y){return !y ? x : gcd (y,x % y);} $\rm l...

Double Sum 2 题意： 求所有有序对一直除以 $2$ 直至为奇数后的值的和。 需要发现一个性质，设 $f_i$ 表示所有能被 $2^i$ 整除的和，则 $f_{i + 1} - f_i$ 表示恰好有 $i$ 个因子 $2$ 的和，那么对于这...

跟着这个题库完善自己的模板。 三角库函数sin(x)/cos(x)/tan(x) 三角函数 asin(x)/acos(x)/atan(x) 反三角函数 atan2(x,y) 返回点 $(x,y)$ 的反正切值，以弧度为单位。返回值的范围是 $[-\p...

部分参考 此处。 通过打表可以找到规律，给出结论： \oplus_{i = 1}^{n} i =\left\{ \begin{aligned} n \ (n \equiv 0 \bmod 4)\\ 1 \ (n \equiv 1 \bmod 4)\\...

主定理【master theorem】本文部分参考《算法导论》。相关证明由于过于复杂，已略去。 前言 $\Theta$ 读作 theta，即等于。 $O$ 读作 big-oh，即小于等于。 $o$ 读作 small-oh，即小于。 $\Omeg...