8113. 【2022.10.7联考noip模拟】Talulah
题意
给定长度为 \(n\) 的排列 \(p\)，定义集合 \(S_i = \{j \mid j \ge i \land \max_{k \in [i,j]} p_k = p_j\}\)。
给定 \(q\) 次询问 \(l,r\)，求 \(\sum_{x,y \in [l,r]} |S_x \cap S_y|\)。
\(n,q \le 2.5 \times 10^5\)
Welcome to Liam's Blog
图论
这里是图论相关的算法笔记。
行列式
定义
定义 \(n\) 阶方阵 \(A\) 的行列式为：
\[
\det A=\begin{vmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\vdots & \vdots & & \vdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\
\end{vmatrix}
=\sum_{p_1,p_2,\cdots,p_n} (-1)^{\tau(p_1,p_2,\cdots,p_n)} \prod_{i=1}^n a_{i,p_i}
\]
其中 \(\{p_1,p_2,\cdots,p_n\}\) 是一个 \(n\) 的排列，\(\tau(p_1,p_2,\cdots,p_n)\) 表示 \(\{p_1,p_2,\cdots,p_n\}\) 的逆序数。
8081.【2024年SD省队集训 day2】反转了 (flip)
题意
给定长度为 \(N\) 的数组 \(A\)，定义 \(S_0 = 0\)，\(S_i = \sum_{j=1}^i A_j(i \in [1,N])\)。
对 \(K \in [0,N]\)，求解：
- 至多反转 \(K\) 个元素的符号，求 \(\max_{i \in [0,N]} {S_i}\) 的最大值。
Miller-Rabin 素性测试
引理1： 费马小定理
\(\forall p \in \mathbb P, 0 \le a \lt p, a^{p-1} \equiv 1 \pmod{p}\)
证明略。
引理2： 二次探测定理
\(\forall p \in \mathbb P, 0 \le x \lt p\)，方程 \(x ^ 2 \equiv 1 \pmod p\) 的解为 \(x \equiv \pm 1 \pmod p\)。
证明略。
设我们要检测的数为 \(n > 2\)。显然 \(n\) 为奇数，设 \(n - 1 = 2^s t\)，其中 \(t\) 为奇数。
若 \(n\) 为素数，我们希望 \(\forall a \in [1,n)\)，满足以下任意条件：
-
\(a^t \equiv 1 \pmod n\)。
-
\(\exists r \in [0,s), a ^ {2 ^ r t} \equiv -1 \pmod n\)。