题意定义图的连通数是每个点可以到达的点数之和，求一个有向图的联通数。其中点数 $N\le 2000$ 。题解显然直接用 $\text{Floyd}$ 传递闭包是不现实的，于是我直接照题解用了bitset。用 bitset $\text{s[i]}$ 表示 $i$ 与 $N$ 个点的连通情况。直接双重循环枚举用 | 合并起来即可。需要注意自己和自己也要算，但给出的矩阵是不算的，所以需要写在后面...
题意给出一个无向图，有下列操作：$(1,a,b)$ ，查询 $a\rightarrow b$ 路径上桥的数量$(0,a,b)$ ，删除边 $(a,b)$ 。保证无论航线如何被破坏，任意时刻任意两点都能够相互到达。其中点数 $N\le 30000$ ，边数 $M\le 100000$ ，操作数 $Q\le 40000$ 。题解显然，桥的数量就是缩完点后两点间的树上距离，动态询问树上距离显然就是...
题意给出一个有向图，有边权 $w_i$ 和点权 $s_i$ 。要求找一个环，使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。其中点数 $N\le 1000$ ，边数 $M\le 5000$ 。题解$0/1$ 分数规划。设当前二分值为 $mid$ ，题目即为$$\dfrac{\sum s_i}{\sum w_i} > mid$$$$\sum (s_i-mid\time...
题意令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目，$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目；则定义：$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$其中点数 $n\le 100$ ，边数 $m\le 4500$ 。题解$n\le 100$ ，又要统计所有节...
题意给出一个 $N$ 点有向图，从 $1$ 到 $N$ ，要求恰好 $T$ 时刻到达。其中 $N\le 10$ ，边权 $\in[1,9]$ 。边权为 $0$ 代表没有边。题解考虑边权只可能为 $1$ 的情况。用 $f[i][j]$ 代表 $i\rightarrow j$ 恰好 $T$ 时刻到达的方案数，那么$$f_T[i][j]=\sum_{k=1}^{N} f_{T-1}[i][k]\t...
题意求不包含子串 $A$ 的长度为 $N$ 的数字 $X$ 的个数。答案对 $K$ 取模。其中 $A$ 的长度 $M\le 20$，$N\le 10^9$，$K\le 1000$ 。题解矩阵乘法优化dp。用 $\text{f[i][j]}$ 表示在 $X$ 中做到第 $i$ 位，匹配到 $A$ 中第 $j$ 位的方案个数。最终的答案即为：$$\sum_{i=0}^{M-1} \text{f[...
题意给出一张无向连通图，求 $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...
题意解同余方程组：$$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$ ，显然偶数位...
概述卢卡斯定理主要用于求解组合数取模问题。公式原命题见： 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$ 个数中选出 $...