Codeforces Luogu 分析 首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。 接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。 我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们...
LOJ 分析 设 $f_i$ 表示 $n=i$ 时的答案，容易得到 直接矩阵快速幂即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <a...
51nod 分析 考虑根号分治。令 $B=\left\lceil\sqrt{n}\right\rceil$，则 $[1,B]$ 内的物品能取完，$[B+1,n]$ 内的物品无法取完。 先考虑 $[1,B]$ 内物品。设 $f_{i,j}$ 表示前 $i$ 种物品和为 $j$ 的方案数，容易写出转移 注意到 $(i,j)$ 的转移点 $(i,k)$ 满足 $k\leq j\land j\eq...
AtCoder Luogu 分析 观察题目中给的这个式子 等价于从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$ 的方案数，等价于从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数。 然后题目中要求的是 $\sum$，因此我们考虑求出以每个 $(-a_i,-b_i)$ 为起点走到每个 $(a_j,b_j)$ 的方案数之和。 注意到 $a_i,b_i$ 的...
Codeforces Luogu 定义 我们可以先找到所有 $g(pre(i))=1$ 的 $i$，再往后扩展。 枚举 $i=|A|$，那么 $g(pre(ik))=1$ 的充要条件是 $S[1..ik-i]=S[i+1..ik]$。 因此我们可以将 $suf(i+1)$ 和 $S$ 匹配，如果匹配长度 $\geq i(k-1)$ 说明合法。 这个匹配的实质是后缀与前缀匹配，因此可以使用...
Luogu 分析 为了方便，把题目里的特征值称为「特征值 A」；再定义一个「特征值 B」表示不弱的 B 的个数。 那么可以将三个问题转化一下： 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k$ 时，请问 X 在哪个位置。 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k-S$ 时，请问 X 在哪个位置。 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $S$ 时，请问...
Codeforces 分析 考虑两个数 $a,b$ 要满足什么条件才可以同时留下。 可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是 显然可以根据 $a,b$ 的奇偶性进行讨论： 若 $a,b$ 都为奇数，则上式...