洛谷5330 [SNOI2019]数论
Luogu LOJ 分析 考虑枚举一个 $A_i$，则我们需要计算 发现 $(Px+A_i)\bmod Q$ 有长度为 $\frac{Q}{\gcd(P,Q)}$ 的循环节，因此我们可以暴力求出循环节，然后计算。这样子是 $\mathcal{O}\left(\frac{nQ}{\gcd(P,Q)}\right)$ 的。 注意到模 $\gcd(P,Q)$ 意义下相等的 $A_i$ 循环节内的...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 考虑枚举一个 $A_i$，则我们需要计算 发现 $(Px+A_i)\bmod Q$ 有长度为 $\frac{Q}{\gcd(P,Q)}$ 的循环节，因此我们可以暴力求出循环节，然后计算。这样子是 $\mathcal{O}\left(\frac{nQ}{\gcd(P,Q)}\right)$ 的。 注意到模 $\gcd(P,Q)$ 意义下相等的 $A_i$ 循环节内的...
Luogu LOJ 分析 考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。 首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。 对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是 可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\...
Luogu LOJ 分析 二进制下每一位模 $3$ 的余数是 $1,2,1,2,\cdots$，也可以看成 $1,-1,1,-1,\cdots$。 假设有 $k$ 个 $1$，我们要将其分配到 $\lceil\frac{n}{2}\rceil$ 个 $1$ 和 $\lfloor\frac{n}{2}\rfloor$ 个 $-1$ 上，使得分配到的 $1$ 和 $-1$ 的和是 $3$ 的倍数...
Luogu UOJ 分析 考虑把每个筐子拆成三个点，三个点间互相连边，然后每个球向能放的筐子拆成的三个点连边。 考虑这张图的一个最大匹配：如果某个筐子匹配了 $0$ 个球，那么会贡献 $1$ 个匹配；如果匹配了 $1$ 个球，那么会贡献 $2$ 个匹配；如果匹配了 $2$ 或 $3$ 个球，那么会贡献 $2$ 或 $3$ 个匹配。 也就是说，半空的筐子贡献的匹配数恰为匹配的球数加 $1$。 ...
Luogu LOJ 分析 显然二合一，先考虑 $m=2$ 的情况。 可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求 用同样的方法扩域计算即可。 代码 // ==================================== // author: M_sea // website: https...
Luogu LOJ 分析 将每个格点拆成四个点，分别表示从这个点往右走、往下走、往左走、往上走。 对每个点维护一个 $nxt$，表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环，我们想办法对其进行维护。 考虑将环拆掉一条边变成一条有向链，并用 LCT 维护这条链。我们同时维护每一段墙是否存在，并修改连进某个点的链。在修改时，我们首先断掉连进来的边，然后再根据墙...
LOJ UOJ 分析 首先可以通过二分用两次询问把第一个字符问出来，假设是 $\texttt{A}$，那么接下来不会再出现 $\texttt{A}$。 考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法，但是实际上可以 $1$ 次询问：设之前的串为 $\texttt{S}$，询问 $\texttt{SBSXBSXXSXY}$，那么如果返回值为 $|S|$ 则这一位为 $\textt...
Codeforces Luogu 分析 首先可以证明图的直径长度不超过 $15$。 先预处理 $f_{i,j}$ 表示 $i$ 走到一个颜色为 $j$ 的点的最短路、$g_{i,j}$ 表示某个颜色为 $i$ 的点走到某个颜色为 $j$ 的点的最短路。这可以通过以每种颜色为起点 BFS 一遍求出。 接着我们枚举 $i$，并试着找到 $j\in[1,i)$ 使得 $dis(i,j)$ 最小。实...
Luogu LOJ 分析 可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。 于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。 代码 // ==================================...
Luogu LOJ 分析 设 $f_i$ 为从 $i$ 点生命值变为 $0$ 点生命值的期望步数，$p_i$ 为生命值 $\geq i$ 时一回合扣掉 $i$ 点生命值的概率，那么有 直接高斯消元是 $\mathcal{O}(n^3)$ 的，只能获得 70 分。 但是这个矩阵很有性质。我们从上往下消，消到每一行时只会有 $3$ 个位置（包括常数项）有值，也就是只要消三列。最后一行时只会剩下...