$\text{memset}$ 作为一个好工具，可以快速对整个数组进行赋值，但有时却因为不知道怎么填中间的一维最后被逼循环复制，这里就贴一点常用的赋值方法。 先解释一下 $\text{memset}$ 函数的用法。 $\text{memset(a, val, sizeof a)}$ 能够初始化一个 ...

传送门 $\text{Solution}$题目意思是求解 \begin{aligned} P &= \sum _{i | n} \dbinom{n}{i}\\ Ans & \equiv G^P \pmod{999911659} \end{aligned}如果没有那个指数，这个题目还是很方便的，直 ...

BSGS（Baby-Step-Giant-Step）算法，用来解决 $A^x \equiv B \pmod{C}(0 \leq x < C)$ 这样的问题。 具体讲BSGS算法之前，先介绍一下离散对数。 在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的 ...

$\text{Lucas}$ 及其拓展定理用于处理 $\dbinom{n}{m} \bmod p$ 的问题，其中 $\text{Lucas}$ 定理处理 $p$ 是质数的情况，而其拓展定理能够处理 $p$ 不是质数的情况。 $\text{Lucas}$若 $p$ 是质数，则对于 $\forall \ ...

中国剩余定理是用于求解线性同余方程组模数两两互质的情形的一种方法。 说人话就是求解以下线性同余方程组： \begin{cases} x \equiv a_1 & \pmod {m_1} \\ x \equiv a_2 & \pmod {m_2} \\ & \dots \\ x \equiv a_ ...

$\text{GCD}$普通的 $\gcd$ 算法相信我不用讲了吧（辗转相除法如果有问题的话应该不会来看我的 $\text{blog}$）。 $\text{ExtendedGCD}$接下来是拓展的欧几里得算法。 拓展欧几里得算法是用来求已知 $(a, b)$ 时，求解一组 $(x, y)$ 使得 $ ...

传送门 $\text{Description}$在基环树上求解最大点独立集问题。 有点学术啊。那我先来解释一下吧。 基环树基环树 顾名思义，就是基于一个环上的树，也就是一个树中有一个环。由于原题中把骑士看成结点，憎恨关系看成边之后就得到了一个有 $n$ 个结点， $n$ 条边的图，我们知道由 $n$ ...

传送门 $\text{Solution}$很容易就能够想到位置和位置上可能的数相匹配，这样子就是二分图最大匹配的问题。 可是那么简单，最有意思的操作在于匹配要求字典序。 这么一来我们要思考一下二分图匈牙利算法实现的特点。 匈牙利算法存在“反悔”操作，也就是说前面匹配好的如果后面需要的话可能会把当前的 ...

传送门 $\text{Solution}$看到这个平方想必都是茫然的。。。 然而有什么方法可以搞掉这个平方呢？数学方法可能比较麻烦。 其实是个套路题 这道题所求的答案就是两个人分别取，取出来的序列相同的方案数 接下来 DP 就稳得一批了 我们用 $dp(k, i, j)$ 表示两个人都取了 $k$ ...

传送门 $\text{Solution}$非常毒瘤的题目。 考场上时一看就知道是线段树维护，可能要用矩阵快速幂，然后就不会了。 实际上就是 线段树维护 + 矩阵快速幂。 做这道题需要有一点前置知识，就是 $\text{Fibonacci}$ 数列是可加的 。 具体怎么说呢，就是有一个第一项是 $x$ ...