题意给出一张无向连通图，求 $S$ 到 $E$ 经过 $N$ 条边的最短路。其中边数 $T\le 100$ ，点的编号 $\le 1000$ ，$N\le 10^6$ 。题解因为是连通图，所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。考虑 $\text{Floyd}$ 的过程：$$\text{dis[i][j]}=\min...
题意在 $R\times C$ 的含障碍的图上把箱子从起点推到终点，人一开始在另一个起点，求人的最短路径。多组数据。$R,C\le 20$题解显然箱子是连续移动的，但人有时需要绕一圈去箱子的背面，所以先对箱子做 $\text{bfs1}$ 。保存一个五元组 $(b_x,b_y,m_x,m_y,now)$ ，表示当前箱子在 $(b_x,b_y)$ ，人在 $(m_x,m_y)$ ，操作序列为 ...
题意给出一个 $n$ 点 $m$ 边的有向图，从 $1$ 出发再回到 $1$ ，途中要逆行一次，问途中最多经过多少个点。$n,m\le 10^{5}$ 。题解显然要缩点，缩点后点权即为连通分量中点的个数 $\text{siz[]}$ 。然后对强连通分量重新建边，正边为 $\text{edge2}$ ，反边为 $\text{edge3}$ 。对正边跑最长路得到以 $1$ 为起点的最长路 $\t...
该合集为乱序版，强度和顺序无关。1ljq：zyt你个龟儿子(几秒后)ljq：我的儿子zyt2wzx：（因当事人墙裂要求删除背景）这凉了啊ljq：没凉，（两秒后），不是很凉，还是有那么一点凉的。3ljq：尔喔（自行脑补发音）4wzx：这是国家发改委指定番目（指《目隐都市的演绎者》）5wzx：ljq中考假期把《方法》和《问题》看完了，而我看完了《目录》（指《路人女主的养成方法》、《我的青春恋爱物...
题意解同余方程组：$$x\times ATK_i\equiv A_i\pmod {P_i}\tag{1}$$$ATK$ 还需要平衡树或者multiset推出来。其中方程个数 $N\le 10^{5}$ ，$A_i\le 10^{12}$ 。题解将原式化简：$$ATK_i\times x+P_i\times y=A_i$$可以用 $\text{exgcd}$ 求出 $x$ 的最小整数解 $S_...
LOJ最优解达成！题意求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数，对 $p$ 取模：是 $2n$ 的全排列奇数项、偶数项分别递增$\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$题解对于性质 $2$ ，可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。分析性质 $3$ ，显然偶数位...
背景OI圈一直盛行一句诗僵卧孤村不自哀，XX AK IOI看似对谁都可以使用，而现实中也确实是这样的。正文但是，经过研究，我发现这其中存在着滥用现象。诗歌讲究的是平仄相对，“僵卧”是“平仄”，这就意味着这个人的名字应该是“仄平”。按照这个规则，那么我校大佬 cyc,wzx,zyt 才适用这首诗。这名字取来就是AK IOI的我这个菜鸡的名字是“平平”，当然不适用。顺便说一句，“IOI”应该念成...
概述卢卡斯定理主要用于求解组合数取模问题。公式原命题见： https://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86原命题等价于：$$\binom{m}{n}=\binom{\lfloor \dfrac{m}{p}\rfloor}{\lfloor \dfrac{n}{p}\rfloor}\times ...
题意把 $n$ 个不同的礼物分给 $m$ 个人，每个人 $w_i$ 个，求方案数 $\mod p$ 的值。其中 $n,p\le 10^{9}$ ，$m\le 5$ 。题解答案显然为：$$\prod _{i=1}^m C(n-\sum_{i=1}^m w_i,w_i)\mod p$$因为 $p$ 不一定是质数，所以直接上 $\text{exLucas}$ 就行了。#include<bit...
反向最优解 $rk3$ 达成。题意求$$\sum_{i=0}^k C_n^i\mod 2333$$其中 $t\le 10^{5} \ , \ n,k\le 10^{18}$题解令 $ha=2333$ ，先用 $\text{Lucas}$ 定理化简$$\sum_{i=0}^k C_{n\div ha}^{i\div ha}\times C_{n\ mod \ ha}^{i\ mod \ ha}...
题意求长度在 $1\sim N$ 之间，由 $[L,R]$ 之间的数构成的单调不降序列的个数。$N,L,R\le 10^{9}$ 。多组数据，组数 $t\le 100$ 。题解令 $M=R-L+1$ ，即可以使用的数的个数。先考虑固定长度为 $n$ 的情况。因为是单调不降，所以数字可以重复使用，而只要选出一部分数就能构成一个且仅有一个满足要求的序列。答案就等价于从 $M+n$ 个数中选出 $...
题意求由 $N\times M$ 的网络上三点构成的三角形个数。$N,M\le 1000$ 。题解图片来源于 https://www.luogu.org/blog/suwakow/solution-p3166每个三角形都可以确定一个最小的包含它的矩形，称这种情况为完全覆盖。那么可以把原矩形化为多个子矩形并只计算完全覆盖的情况。显然对于每个长宽相同的子矩形，它们对答案的贡献都是相同的，所以只用...
题意定义$$P=\sum_{i-1}^n i|n\ C_n^i$$求$$G^P\mod 999911659$$其中 $N,P\le 10^{9}$ 。题解由拓展欧拉定理得$$G^P\equiv G^{P\mod \varphi(999911659)} \pmod {999911659}$$因为 $999911659$ 是质数，所以$$\varphi(999911659)=999911658$...
题意求一个位数 $\geq 2$ 的 $2^{k}$ 进制数 $r$ ，满足：化为二进制后位数 $\le w$每一位上的数依次递增其中 $k\le 9 \ , \ k\le w\le 30000$ ，保证 $r$ 化为 $10$ 进制的位数 $\le 200$ 。题解对于条件 $1$ ，显然 $r$ 的位数 $L \le \lceil \dfrac{w}{k}\rceil $ 。当 $L\l...
题意给出 $A,B,X_1,p,t$ ，数列 $X_i$ 满足递推式：$$X_{i+1}\equiv A\times X_i+B\pmod p$$求使 $X_i\equiv t\pmod p$ 成立的最小的 $i$ 。题解一般情况列出来找下规律：$$\begin{cases}X_2\equiv A\times X_1+B\pmod p \\X_3\equiv A^{2}\times X_1+...