跳转至

Welcome to Liam's Blog

  • 分类于 GMOJ
  • 需要 2 分钟阅读时间

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\)

思考

考虑钦定 \(x<y\)，如下图所示：

图解

发现 \(\forall i \ge y\)，\(i \in S_x \Rightarrow i \in S_y\)。

Proof: 因为 \(i \in S_x\)，所以 \(\max_{k \in [x,i]} p_k = p_i\)，因此显然 \(\max_{k \in [y,i]} p_k = p_i\)，即 \(i \in S_y\)。\(\square\)

因此 \(|S_x \cap S_y| = |S_x \cap [x,y)| + |S_y|\)。

考虑把这两个部分分开处理，发现所有 \(|S_y|\) 即为 \(\sum_{i \in [l,r]} (i-l)|S_i|\)，可以用前缀和 \(\mathrm O(1)\) 计算。

考虑计算 \(\sum_{l \le x \lt y \le r} |S_x \cap [x,y)|\)，如下图所示：

图解

正难则反，考虑抛弃 \(y\) 的限制，而是计算 \(i \in S_x\) 的贡献。

发现 \(\forall i \in S_x \cap [x,r]\)，对于 \(\forall y \gt i\) 都有 \(1\) 的贡献，即原式等于 \(\sum_{i \in S_x \cap [x,r]} r-i\)。

发现这个不好维护，于是正难则反，考虑计算 \(\forall i \in [l,r]\) 对 \(x \le i\) 的贡献。

记 \(\mathrm{pre}_i = \max_{j \lt i} {j \mid p_j \gt p_i}\)，即 \(i\) 前第一个大于 \(i\) 的元素的位置，并记 \(p_0 = \infty\)。

发现 \(\forall i \in [l,r]\)，\(i\) 对 \(x \in (\mathrm{pre}_i,i]\) 有 \(r-i\) 的贡献。

由于我们不清楚 \(r\) 的值，因此我们维护 \(r\) 的系数即可。

图解

如上图，考虑用线段树维护区间加与区间和。

考虑 \(i \in [l,r]\) 这条限制，容易发现当 \(i \lt l\) 时，\(i\) 对 \([l,r]\) 无贡献；当 \(i \gt r\) 时，如上图的 \(j\)，会对 \([l,r]\) 产生多余的贡献。

因此我们把询问离线并按右端点排序，依次加点即可。

最后别忘了我们计算的是 \(x \lt y\) 的答案，剩下部分是 naive 的。

如果强制在线的话，可以用可持久化线段树 + 标记永久化解决，时间复杂度同为 \(\mathrm O((n+q) \log n)\)。

  • 分类于 Graph
  • 需要 1 分钟阅读时间

图论

这里是图论相关的算法笔记。

  • 分类于 Math
  • 需要 5 分钟阅读时间

行列式

定义

定义 \(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\}\) 的逆序数。

引理

Lemma 1

\[ \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 \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = k \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 2

\[ \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = -\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_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 3

若矩阵有相同的两行，则行列式为零。

Proof: 交换相同的两行后矩阵不变，且由 Lemma 2 得行列式变号，即 \(|A|=-|A|\)，所以 \(|A|=0\)。\(\square\)

Lemma 4

若矩阵某一行是另一行的倍数，则行列式为零。

Proof: 由 Lemma 1 & Lemma 3 易证。

Lemma 5

若 \(\forall j,a_{i,j} = b_j + c_j\)，则

\[ \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \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 \\ b_1 & b_2 & \cdots & b_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} + \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 \\ c_1 & c_2 & \cdots & c_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

读者自证不难。

Lemma 6

\[ \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

Proof: 设

\[ 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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}, B = \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \\ C = \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_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \]

由 Lemma 4 得 \(|B|=0\)，由 Lemma 5 得 \(|C| = |A| + |B| = |A|\)。\(\square\)

Lemma 7

\[ \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ 0 & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{n,n} \\ \end{vmatrix} = \prod_i a_{i,i} \]

即上三角矩阵的行列式为主对角线元素的乘积。

Proof: 由行列式的定义得若 \(\exists i, a_{i,p_i} = 0\)，那么整个排列对行列式无贡献。

因此要想对行列式有贡献，\(p_n\) 必等于 \(n\)，同理得 \(\forall i, p_i = i\)。\(\square\)

求解

显然有 \(\mathrm O(n! n)\) 的 naive 方法，但如果这样上面的 \(\LaTeX\) 就白写了（

考虑把矩阵转化为上三角矩阵并由 Lemma 7 \(\mathrm O(n)\) 计算行列式。

这个过程形如高斯消元，于是考虑用高斯消元法来求解行列式。

假设目前处理到第 \(i\) 行，要使得 \(\forall j > i, a_{j,i} = 0\)。

显然可以让第 \(j\) 行加上第 \(i\) 行乘 \(- \frac{a_{i,j}}{a_{i,i}}\)，但对于任意模数情况下 \(a_{i,i}\) 不一定有逆元。

因此，我们考虑用辗转相除法。

每次使得 \(a_{j,i} \gets a_{j,i} \bmod a_{i,i}\)，并交换第 \(i\) 行与第 \(j\) 行，直到 \(a_{i,i}\) 为 \(0\)。

即让第 \(j\) 行加上第 \(i\) 行乘 \(- \lfloor \frac{a_{i,j}}{a_{i,i}} \rfloor\)。

时间复杂度看似是 \(\mathrm O(n^3 \log P)\)，但可以证明是 \(\mathrm O(n^3)\)，其中 \(P\) 是模数。

参考代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int n,p,a[N + 2][N + 2];
int det() {
    int sgn=0;
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j) {
            while(a[i][i]) {
                ll d=a[j][i]/a[i][i];
                for(int k=1; k<=n; ++k)
                    a[j][k]=(a[j][k]-d*a[i][k]%p)%p;
                swap(a[i],a[j]);
                sgn^=1;
            }
            swap(a[i],a[j]);
            sgn^=1;
        }
    ll ans=sgn?-1:1;
    for(int i=1; i<=n; ++i) ans=ans*a[i][i]%p;
    return (ans+p)%p;
}

应用

  • 矩阵树定理
  • 分类于 GMOJ
  • 需要 2 分钟阅读时间

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}\) 的最大值。

朴素解法

暴力枚举 \(K\)，并枚举 \(i \in [0,N]\)，假定 \(S_i = \max_{j \in [0,N]} {S_j}\)，显然最优方案为反转前 \(i\) 个元素中绝对值最大的 \(K\) 个元素。

设 \(B_i = \max(0,-A_i)\)，那么第 \(i\) 段前缀对 \(K\) 的贡献为 \(C(i,K) = S_i + 2 W(i,K)\)，其中 \(W(i,K)\) 为 \(\{B_1,B_2,\dots,B_i\}\) 中的前 \(K\) 大元素的和。

答案即为 \(\max{C(i,K)}\)。

注意当 \(i \lt K\) 时，\(W(i,K) = \sum_{j=1}^i B_j\)。

\(W(i,K)\) 可以用主席树在 \(O(\log N)\) 时间内求得。

总时间复杂度 \(O(N ^ 2 \log N)\)，期望得分 30。

优化

设 \(f_K\) 表示 \(\min \{i | \forall j,C(i,K) \ge C(j,K)\}\)，即使得 \(C(i,K)\) 最大的最小的 \(i\) 值。

容易发现 \(f\) 非严格单调递增。

于是便如 ABC348G 一样，用分治 + 主席树解决。

单调性证明

实践是检验真理的唯一标准 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n,a[N + 2];
long long s[N + 2];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=1; i<=n; ++i) s[i]=s[i-1]+a[i];
    int lst=-1;
    for(int i=0; i<=n; ++i) {
        multiset<int> st;
        ll sum=0,ans=0,k=0;
        for(int j=1; j<=n; ++j) {
            if(i!=0&&a[j]<0&&(st.size()<i||*st.begin()<-a[j])) {
                if(st.size()==i) {
                    sum-=*st.begin();
                    st.erase(st.begin());
                }
                sum+=-a[j];
                st.insert(-a[j]);
            }
            if(s[j]+sum*2>ans) ans=s[j]+sum*2,k=j;
        }
        assert(lst<=k);
        lst=k;
        printf("%lld ",ans);
    }
    return 0;
}

考虑使用反证法，假设 \(\exists i,f_i > f_{i+1}\)，设 \(f_i = x,f_{i+1} = y\)。

因为 \(f_i = x\)，于是有

\[ \begin{aligned} & C(y,i) \lt C(x,i) \\ & S_y + 2W(y,i) \lt S_x + 2W(x,i) \\ & S_y - S_x + 2W(y,i) - 2W(x,i) \lt 0 \\ \end{aligned} \]

因为 \(f_{i+1} = y\)，于是有

\[ \begin{aligned} C(y,i+1) & \ge C(x,i+1) \\ S_y + 2W(y,i+1) & \ge S_x + 2W(x,i+1) \\ S_y - S_x + 2W(y,i+1) - 2W(x,i+1) & \ge 0 \\ & \gt S_y - S_x + 2W(y,i) - 2W(x,i)\\ W(y,i+1) - W(x,i+1) & \gt W(y,i) - W(x,i) \\ W(y,i+1) - W(y,i) & \gt W(x,i+1) - W(x,i) \\ \end{aligned} \]

这显然是矛盾的，因为 \(y<x\)，\(W(y,i+1) - W(y,i)\) 相当于 \(\{B_1,B_2,\dots,B_x\}\) 中的第 \(i+1\) 大的元素，但是 \(\{B_1,B_2,\dots,B_y\} \subset \{B_1,B_2,\dots,B_x\}\)，于是必有 \(W(y,i+1) - W(y,i) \le W(x,i+1) - W(x,i)\)，矛盾。

因此，\(f\) 是非严格单调递增的。

其他例题

  • 分类于 Number Theory
  • 需要 2 分钟阅读时间

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\)。

证明

若以上两项都不满足，显然有 \(a^t \not \equiv 1 \pmod n\)，这时分两类讨论：

  • \(a ^ {n-1} \not \equiv 1 \pmod n\)，根据费马小定理，显然 \(n\) 不是素数。

  • \(a ^ {n-1} \equiv 1 \pmod n\)，又因为 \(\forall i \in [0,s), a ^ {2 ^ i t} \not \equiv -1 \pmod n\)，显然有 \(\exists i \in [0,s), a ^ {2 ^ i t} \not \equiv -1 \pmod n\) 且 \(a ^ {2 ^ {i + 1} t} \equiv 1 \pmod n\)。 即 \(\exists x \in [2,n-1), x ^ 2 \equiv 1 \pmod n\)，根据二次探测定理，\(n\) 不是素数。

当 \(n\) 为合数，若 \(a\) 仍满足上述两项之一，则称 \(a\) 为 \(n\) 的强伪证；若 \(a\) 不满足上述两项，则称 \(a\) 为 \(n\) 不是素数的凭证。

每个奇合数都有许多凭证，但是要找到他们不容易。于是考虑多随机几个 \(a\)，以验证 \(n\) 的素性。

code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
bool miller_rabin(ll n) {
    if(n<3) return n==2;
    if(n%2==0) return false;
    ll s=n-1,t=0;
    while(s%2==0) s/=2,++t;
    for(int i=0; i<8; ++i) {
        ll x=randint(2,n-1),u=qpow(x,s,n);
        if(u==1) continue;
        {
            int j;
            for(j=0; j<t; ++j) {
                if(u==n-1) break;
                u=mul(u,u,n);
            }
            if(j==t) return false;
        }
    }
    return true;
}