${\color{Red} \mathrm{写的很垃圾，待补充} } $
Update on 2023.11.17 修改笔误，补充内容。
题目大意
求 $m!$ 在模 $p$ 下的值，保证 $p$ 是素数。
分析与解答
考点：威尔逊定理。
由威尔逊定理可知，若 $p$ 为素数，则有$(p-1)! \equiv p-1\pmod{p}$。
可通过以上定理得 $(p-1)! \pmod{p}$ 的值。
若 $m \ge p$，结果为 $0$。
若 $m < p$，题目中让我们求的是：
$$\prod_{1}^{m} \pmod{p}$$
但我们已知：
$$\prod_{1}^{p - 1} \pmod{p}$$
所以就需要乘上以下式子，来删去多余的部分。
$$\prod_{i=m+1}^{p-1} i^{-1} \pmod{p}$$
最终的答案为：
$$(p-1) \times \prod_{i=m+1}^{p-1} i^{-1} \pmod{p}$$
求逆元可通过费马小定理实现。
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a, long long b, long long p) {
long long ans = 1;
while (b) {
if (b & 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int main() {
freopen("factorial.in", "r", stdin);
freopen("factorial.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
long long m, p;
cin >> m >> p;
if (m >= p)
cout << 0 << '\n';
else {
long long ans = p - 1;
for (long long i = p - 1; i > m; i--) ans = 1ll * ans * qpow(i, p - 2, p) % p;
cout << ans << '\n';
}
}
return 0;
}
题目大意
分析与解答
考点：分块
这道题的 做法很多。
考虑建立反图，用线段树优化。
对于每一个点构建全局线段树，在连边的时候由更大的节点向更小的节点连边。但每个点连出的边是 $O(\log n)$ 的，再跑一遍最短路，整体时间复杂度变为 $O(n \log^2 n)$ 不能通过这道题目。
因为每条边的边权可以定为 $1$ ，每个点在第一次达到时直接扔进队列里，故可不用优先队列完成这道题。时间复杂度 $O(n\log n)$，理论上不能通过此题。写的优秀可以得 86pts。
发现不能再通过线段树进行优化，考虑在构建返图时不连那么多边来优化程序。发现 $(n-L+R) \times d^{-1}$ 就可以得到我们所需要的点。例如 :
$$n = 10,d = 4, \gcd(n, d) = 2，L=1,R=3$$
没有必要一次性把图全部构建出来，因为构建出来就已经爆了。
分析与解答
考点： 整体二分
莫队部分分，背包合并部分分
需要进行离线操作，并且把每一种询问都扯上关系，背包合并不行。
考虑整体二分和分治。
对于每一个背包做前缀最大值处理，后缀也处理了，可以 $O(m)$ 查询，后使用整体二分。
分析与解答
考点：最小生成树的理解。（容斥原理？）
当 $m = n - 1$ 时，每一条道路都是需要取，利用贪心排序后枚举每一条边的长度即可通过一部分分。准确证明不会。树边均可这样操作。将这个方法衍生到非树边，也是因该边权从小到大加。
还是先进行排序，但是在选择的时候需要注意之前已经被选过的情况，，然后，然后就做出来了。
总结
- 对于乘法逆元的运用还是不熟悉
- 第四题虽然有思路，而且是正解，但是没有实现出来，码力太弱。
- 每道题还是要先打一下暴力再去做正解。
- 注意部分分推广
题解
A. 虫群之心
威尔逊定理板子题，注意题目条件。
B. 喝醉的兔子
算法一
对于subtask1，过程唯一，可以直接暴力。
算法二
令 $f_i$ 表示模 $n$ 余 $i$ 时的最少步数，考虑建图。
对于 $L = R$ 的点边数不多，bfs 一遍即可。能过 subtask1, 2, 5。
算法三
考虑 $L\neq R$ 时的建图，可以用线段树之类的优化建图。
最后再用单调队列之类的方法做一下即可。
复杂度差不多是 $O(T (n \lg n + q))$
能过 subtask1, 2, 3, 4，或许能过 subtask5, 6。
算法四
考虑维护 $gi = \min{0\le j\le R−L}\ f_{(i+j)} \mod\ n$，建图 bfs，可以优化常数，降低代码复杂度。
然后可以再用线段树之类的优化建图。
算法五
考虑 bfs 的过程，每个点第一次被遍历到的时候它的最终答案就确定了。
所以我们只需要每次考虑在一段区间内把所有未标记的节点找出来即可。
相当于删点查后继，使用 set 即可。
复杂度和算法三类似。
算法六
对于删点查后继问题，可以使用并查集或者类似四毛子的方法维护。
复杂度 $O(Tn\alpha(n))$ 或 $O(Tn)$。
注意一下常数就能AC。
算法七
沿着算法五的思路，给序列分块，$R-L$ 个一块，容易发现每个块内任意时刻都是一个前缀和一个后缀被删除。所以只需要给每个块定两个指针。修改只会涉及到 $O(1)$ 个块。每个块单独维护一下即可。
复杂度 $O(Tn)$，能AC。
算法八
回到优化建图的思路上来，再结合一下算法七。可以得到一个 $O(Tn)$ 的优化建图的做法。
注意下常数能AC。
其它想法
如果这个题改成求最优解概率，仍然可以扩展算法八的做法解决。但使用算法六或算法七的方法似乎不太可行。
C. 盲盒流水线
算法一
直接暴搜。
可以过掉 subtask1，15分。
算法二
每次暴力dp，复杂度 $O(qnm)$。
算法三
考虑到合并两个背包复杂度为 $O(m^2)$。
所以用线段树之类的数据结构维护可以做到 $O(nm^2 + qm^2\lg n)$。
算法四
我们有两种背包的操作可以做到复杂度 $O(m)$：一种是往背包里加入一个元素，一种是询问两个背包合并后价格总和不超过某个定值的答案。
我们可以考虑分治，对于一段背包的区间 $[l, r]$，如果足够小，我们可以暴力所有的询问。
否则可以取中点 $mid = \lfloor \frac{l+r}2\rfloor$，从 $mid$ 往两边分别做前缀/后缀背包，那么此时每个过中点的询问可以视为两个已处理出来的背包合并后询问价格总和不超过 $m$ 的答案，可以直接 $O(m)$ 解决。
那么此时没有过中点的询问，所以可以分治解决 $[l, m]$ 和 $[m + 1, r]$。
复杂度 $O(nm \lg n + qm)$，100分。
D. 失落的帝国
当 $m=n-1$ 时，问题转化成有 $m$ 个变量，第 $i$ 变量的取值为 $\left[l_i, r_i\right]$，且任意两个变量不相等，构造一组方案。我们可以将所有区间按照左端点排序，随后扫 $l_i$ 时贪心的选择 $r_i$ 最小的来放置。
当 $m>n-1$ 时，每条非树边会有额外的限制：非树边 $(u, v)$ 的长度必须严格大于路径 $u \rightarrow v$ 的长度最小值。因此，对于一条非树边，我们只有在这条路径上所有的边均被赋值后，才可以赋非树边的值。因此我们仍然按照 $l_i$ 排序，但在合并两个联通块时，更新这一轮所联通的非树边，如果一个非树边的两端点联通，则将其加入堆中即可。
总的时间复杂度为 $O\left((n+m) \log ^2 n\right)$ 或 $O((n+m) \log n)$ 。