link。

简单提一下做法，注意到 $k^{2^a}\equiv k^{2^b}\equiv-1\equiv (-1)^{2^{b-a}}=1\pmod{(k^{2^a}+1,k^{2^{b}}+1)}$，所以 $\gcd$ 只会是 $1$ 或 $2^{r-l}$，取决于 $k$ 的就行，于是求一个 product 即可。

接下来是这篇题解的重点，聚焦 $\displaystyle \prod\left(k^{2^i}+1\right)=\sum_{i=0}^{2^{r-l+1}-1}\left(k^{2^l}\right)^i$ 做补充。

不妨从二项式乘法的角度来看，举例 $\left(k^{2^i}+1\right)\left(k^{2^j}+1\right)\left(k^{2^w}+1\right)$，不妨将 $k^{2^x}$ 看作是选择，将 $1$ 看作是不选择，那么一个长度为 $r-l+1$ 的二进制数即可表示出这个乘积所有的状态，不妨设这个状态为 $S$，注意到 $S$ 对答案的贡献是在做加法，并且因为类似 $2^i+2^j+2^w$ 的指数相加正好可以凑出 $S$，所以 $S$ 的贡献就是 $\left(k^{2^l}\right)^S$，得证。

void executer() {
    int k, p;
    LL l, r;
    cin >> k >> l >> r >> p;
    SetMod(p-1);
    int e = qpow(2, l), e2 = qpow(2, r-l+1);
    SetMod(p);
    int K = k%p ? qpow(k, e) : 0, ans;
    if (K == 0) {
        ans = 1;
    }
    else {
        if (K == 1) {
            ans = qpow(2, r-l+1);
        }
        else {
            ans = mul(sub(qpow(K, e2), 1), inv(sub(K, 1)));
        }
    }
    if (k%2) {
        mul_eq(ans, inv(qpow(2, r-l)));
    }
    cout << ans << "\n";
}

前置容斥原理，最精简的形式应当如此写成：

有 $n$ 个集合 $A_1, \dots, A_n$，记 $S = \{A_1, \dots, A_n\}$。

则有 $\displaystyle\left|\bigcup_{i = 1}^n A_i\right|=\sum_{T\in2^{S}}(-1)^{|T|-1}\left|\bigcap_{X\in T}X\right|$。

考察欧拉函数通项公式，不妨从容斥的角度来理解：

欲证明 $\displaystyle\varphi(n) = n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)$。

P.f.：令 $A_i$ 表示 $p_i$ 的倍数集合（共 $k$ 个这样的集合），并且这些倍数 $\leqslant n$，$S = \{A_1, \dots, A_k\}$，可知 $\left|A_i\right| = \lfloor\frac{n}{p_i}\rfloor$。则 $\displaystyle\varphi(n) = n-\left|\bigcup_{i=1}^k A_i\right|=n-\sum_{T\in2^{S}}(-1)^{|T|-1}\left|\bigcap_{X\in T}X\right|=n-\sum_{T\in2^{S}}(-1)^{|T|-1}\frac{n}{\prod p}=n-\left(\sum_{i=1}^k\frac{n}{p_i}\right)+\left(\sum_{i=1}^k\sum_{j=i+1}^{k}\frac{n}{p_ip_j}\right)-\cdots=n
\left(1-\left(\sum_{i=1}^k\frac{1}{p_i}\right)+\left(\sum_{i=1}^k\sum_{j=i+1}^{k}\frac{1}{p_ip_j}\right)-\cdots\right) = n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$。

解释一下推导的最后一步，考虑组合意义，r.h.s. 相当于在多项式凑系数，$1$ 表示不选，$\frac{1}{p}$ 表示选，选奇数个符号为负，选偶数个符号为正恰好对应 l.h.s.（我觉得能从左边推到右边还是比较困难的）。

从积性的角度：

P.f.：易证 $\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}$（考虑按 $[1,\dots p], [p+1, \dots, 2p], \dots, [p^{\alpha-1}+1, p^\alpha]$ 分组，发现只有每组的最后一个数 $\not\perp p^\alpha$，而这样的组一共有 $p^{\alpha-1}$），那么 $\displaystyle\varphi(n) = \prod_{i=1}^k\varphi(p_i^{\alpha_{i}}) = \prod_{i=1}^k\left(p_i^{\alpha_{i}}-p_i^{\alpha_i-1}\right)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$。

结合以上两种证明可以顺便证明欧拉函数的积性。

写出 CRT 所解决的线性同余方程组问题：

求解方程 $x\equiv a_i\pmod{p_i}$。

Sol.：考虑构造

咕咕咕

类欧几里得。

给定非负整数 $n,a,b,c$，求 $f(n, a, b, c) = \displaystyle\sum_{i=1}^n\lfloor\frac{ai+b}{c}\rfloor$

Sol. pt 1：首先若 $a\geqslant c$，或 $b\geqslant c$ 我们可以通过对取模并提前计算贡献的方式将 $a<c$，$b<c$ 的假设一般化。于是不妨设 $a<c$，$b<c$，设 $m=\lfloor\frac{an+b}{c}\rfloor$，也就是求和项中的最大值（非负整数），由于 $\displaystyle\forall x\in\mathbb{N},x=\sum_{i=1}^{+\infty}[i \leqslant x]$，所以原式等于 $\displaystyle\sum_{i=1}^n\sum_{j=1}^{m}[j \leqslant \lfloor \frac{ai+b}{c} \rfloor]=\sum_{j=1}^m \sum_{i=1}^n [ai \geqslant cj-b]=nm-\sum_{j=1}^m \sum_{i=1}^n [ai \leqslant cj-b-1]=nm-\sum_{j=1}^m \sum_{i=1}^n [i \leqslant \lfloor\frac{cj-b-1}{a}\rfloor] = nm-f(m, c, -b-1, a)$，到这里你会发现有点不对头，我应该要保证 $-b-1$ 是非负整数，但是这不太可能，考虑到 $b$ 这个位置贡献的方式，我们也许需要考虑更改 $f$ 的定义。

Sol. pt 2：更改定义 $f(n, a, b, c) = \displaystyle\sum_{i=\color{red}0}^n\lfloor\frac{ai+b}{c}\rfloor$，推导过程大体相同（有些细节可以参看 $g$，$h$ 的推导），最终的结论是 $f(n, a, b, c) = nm-f(m-1, c, c-b-1, a)$，这保证了非负整数的前提（注意边界条件的计算有所改变）。

让我们定义 $\displaystyle s_k(n) = \sum_{i=1}^n i^k$。

大致代码长这样：

int floor_sum(LL n, int a, int b, int c) {
    // @returns: \sum_{i=0}^n floor((ai+b)/c)
    if (a == 0) {
        return mul(safe_mod(n+1), safe_mod(b/c));
    }
    if (a >= c || b >= c) {
        return add(floor_sum(n, a%c, b%c, c), mul(s(n), safe_mod(a/c)), mul(safe_mod(n+1), safe_mod(b/c)));
    }
    LL m = (a*n+b)/c;
    return sub(mul(safe_mod(n), safe_mod(m)), floor_sum(m-1, c, c-b-1, a));
}

给定非负整数 $n, a, b, c$，求 $g(n, a, b, c) = \sum_{i=0}^n \lfloor\frac{ai+b}{c}\rfloor^2$，$h(n, a, b, c) = \sum_{i=0}^n i\lfloor \frac{ai+b}{c} \rfloor$

__Sol.__：汲取先前的教训，我们将 $0$ 囊括进了和式。同时在看了题解推导的过程后，我们可以更加成熟地对问题进行分类讨论。

• $g$

  • $c \leqslant \max\{a, b\}$：$\displaystyle g(n, a, b, c) = \sum_{i=0}^n \left( \lfloor\frac{(a\bmod c)i+b\bmod c}{c}+i \lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c} \rfloor \rfloor \right)^2 = g(n, a \bmod c, b \bmod c, c)+2\lfloor \frac{a}{c} \rfloor h(n, a\bmod c, b \bmod c, c) + 2 \lfloor \frac{b}{c} \rfloor f(n, a \bmod c, b \bmod c, c) + s_2(n)\lfloor \frac{a}{c} \rfloor ^ 2 + n(n+1)\lfloor \frac{a}{c} \rfloor \lfloor \frac{b}{c} \rfloor + (n+1)\lfloor \frac{b}{c} \rfloor ^ 2$。
  • $c > \min\{a, b\}$：首先注意到 $x^2 = x(x+1)-x = 2s_1(x) - x$，令 $m=\lfloor \frac{an
    +b}{c} \rfloor$，因此 $\displaystyle g(n, a, b, c) = \sum_{i=0}^n \lfloor \frac{ai+b}{c}^2 \rfloor = 2\left(\sum_{i=0}^n \sum_{j=1}^{\lfloor \frac{ai+b}{c} \rfloor}j\right)-\left(\sum_{i=0}^n\lfloor \frac{ai+b}{c} \rfloor\right) = 2\left(\sum_{i=0}^n\sum_{j=0}^{m-1
    } (j+1)[j < \lceil \frac{ai+b-c+1}{c} \rceil]\right) - f(n, a, b, c) = 2\left(\sum_{j=0}^{m-1
    } (j+1) \sum_{i=0}^n [i > \lfloor \frac{cj-b+c-1}{a} \rfloor]\right) - f(n, a, b, c) = 2\left(\sum_{j=0}^{m-1
    } (j+1) \left(n - \lfloor \frac{cj-b+c-1}{a} \rfloor\right)\right) - f(n, a, b, c) = 2n\times s_1(m) - 2h(m-1, c, c-b-1, a) - 2f(m-1, c, c-b-1, a) - f(n, a, b, c)$。

• $h$

  • $c \leqslant \max\{a, b\}$：$h(n, a, b, c) = h(n, a \bmod c, b \bmod c, c) + s_1(n) \lfloor \frac{b}{c} \rfloor + s_2(n) \lfloor \frac{a}{c} \rfloor$。
  • $c > \min\{a, b\}$：$\displaystyle h(n, a, b, c) = \sum_{i=0}^n i\lfloor \frac{ai+b}{c} \rfloor = \sum_{i=0}^ni\sum_{j=0}^{m-1}[cj < ai+b-c+1] = \sum_{j=0}^{m-1}\sum_{i=0}^ni[i > \lfloor \frac{cj+c-b-1}{a} \rfloor] = \sum_{j=0}^{m-1}\left(s_1(n)-\sum_{i=0}^n i[i \leqslant \lfloor \frac{cj+c-b-1}{a} \rfloor]\right) = \sum_{j=0}^{m-1} s_1(n)-s_1(\lfloor \frac{cj+c-b-1}{a} \rfloor) = m\times s_1(n)-\frac{\sum_{j=0}^{m-1}\left(\lfloor \frac{cj+c-b-1}{a} \rfloor^2+\lfloor \frac{cj+c-b-1}{a} \rfloor\right)}{2} = s_1(n)\times m - f(m-1, c, c-b-1, a) - g(m-1, c, c-b-1, a)$。

考试给👴遇到了就下地狱吧。

最后的代码还是有点说头，很诡秘的是，用函数式取模会 T 飞，三个函数一起写会 Wa，反正最后的结局就是 modint+抄代码。

tpl floor_sum(LL n, int a, int b, int c) {
    if (a == 0) {
        return {mi(n+1)*(b/c), mi(n+1)*sqr(b/c), s(n)*(b/c)};
    }
    if (a >= c || b >= c) {
        tpl ret = floor_sum(n, a%c, b%c, c);
        return {
            ret.f+s(n)*(a/c)+mi(n+1)*(b/c),
            ret.g+mi(2)*(a/c)*ret.h+mi(2)*(b/c)*ret.f+s2(n)*sqr(a/c)+mi(2)*s(n)*(a/c)*(b/c)+mi(n+1)*sqr(b/c),
            ret.h+s(n)*(b/c)+s2(n)*(a/c)
        };
    }
    LL m = (a*n+b)/c;
    tpl ret = floor_sum(m-1, c, c-b-1, a);
    return {
        mi(n)*m-ret.f,
        mi(2)*n*s(m)-2*ret.h-2*ret.f-(mi(n)*m-ret.f),
        s(n)*m-ret.f*iv2-ret.g*iv2
    };
}

阶，原根，还有，，？

学数论，就好比吃shit。吃shit啊吃shit

阶 multiplicative order：在 $(a, m) = 1$ 的情况下，极小的满足 $a ^ n \equiv 1 \pmod m$ 的正整数 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。

由于欧拉定理，所以阶一定存在（至少有一个 $\varphi(m)$）。接下来扯几个性质：

• $\{1, a^2, \dots, a^{\delta_m(a)}-1\}$ 是模 $m$ 的缩系。

link。

如果做过 codeforces - 1144G 那这题最多 *2200。

序列中的最大值必然为其中一个拐点，不妨设 $a_p = a_\max$，先讨论另一个拐点 $i$ 在 $p$ 左侧的情况。于是问题转化为规划 $[1, i)$，$(i, p)$，$(p, n]$ 几个区间中的数给 $i$ 还是给 $p$。

• 对于 $[1, i)$，令 $dp[i]$ 表示将 $[1, i]$ 分为两个 strictly increasing subsequence，其中不以 $i$ 结尾的 subsequence 的结尾元素的最小值，分讨转移即可。
• 对于 $(i, p)$，同 codeforces - 1144G，which is 这题唯一的难点。
• 对于 $(p, n]$，同情况 1。

不太会写代码，，，参考了下 editorial，，，

#include <bits/stdc++.h>
#define cm(x, y) x = min(x, y)
#define cm2(x, y) x = max(x, y)
using namespace std;
int n, a[500100], pos, dp[500100], dp2[500100], dp3[500100][2];
int solve() {
    pos = n;
    for (int i=0; i<n; ++i) {
        if (a[i] > a[pos]) {
            pos = i;
        }
    }
    dp[0] = -1;
    for (int i=1; i<=pos; ++i) {
        dp[i] = 1e9;
        if (a[i] > dp[i-1]) {
            cm(dp[i], a[i-1]);
        }
        if (a[i] > a[i-1]) {
            cm(dp[i], dp[i-1]);
        }
    }
    dp2[n-1] = -1;
    for (int i = n-2; i>=pos; --i) {
        dp2[i] = 1e9;
        if (a[i] > dp2[i+1]) {
            cm(dp2[i], a[i+1]);
        }
        if (a[i] > a[i+1]) {
            cm(dp2[i], dp2[i+1]);
        }
    }
    int res = 0;
    dp3[pos][0] = dp[pos];
    for (int i=pos+1; i<n; ++i) {
        dp3[i][0] = 1e9;
        dp3[i][1] = -1e9;
        if (a[i-1] > a[i]) {
            cm(dp3[i][0], dp3[i-1][0]);
        }
        if (dp3[i-1][1] > a[i]) {
            cm(dp3[i][0], a[i-1]);
        }
        if (a[i-1] < a[i]) {
            cm2(dp3[i][1], dp3[i-1][1]);
        }
        if (dp3[i-1][0] < a[i]) {
            cm2(dp3[i][1], a[i-1]);
        }
        res += dp3[i][1] > dp2[i];
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    int ret = solve();
    reverse(a, a+n);
    cout << ret+solve() << "\n";
}

今天比较重要的 qq 号被封了，心情很不好。在极权主义国家里享受新闻自由与言论自由 when？never probably for sure。

欧拉相关

• 无向图

  • 欧拉回路判定：（1）连通（2）没有奇度结点；
  • 欧拉通路判定：（1）连通（2）恰有 $0$ 或 $2$ 个奇度结点；

• 有向图

  • 欧拉回路判定：（1）连通【指任意顺序的任意点对可达】（2）每个点出入度相同；
  • 欧拉通路判定：（1）边无向化后连通（2）最多一个点出入度差 $1$（3）最多一个点入出度差 $1$（4）其他点出入度相同；

哈密顿相关

懒得。

Copyright Quack.

拟阵?type=header

拟阵的定义与常见性质 & 拟阵交算法

拟阵的定义与常见性质

独立集系统和拟阵

定义独立集系统$S=(E，\mathcal{I})$，$E$是基本元素的集合，$\mathcal{I} \subseteq 2^{E}$，$\mathcal{I}$中的元素称为独立集。

$\mathcal{I}$需要满足遗传性：如果$A \in \mathcal{I}，B \subseteq A$，那么$B \in \mathcal{I}$。

举例：

定义在无向图$G(V，E)$上的独立集系统，$\mathcal{I}$是不构成环的边集合，显然满足遗传性。

求无向图的最大生成树，实际上是先给$E$中每个元素赋予一个权值(边权)，然后求一个权值最大的独立集。

回忆一下kruskal算法，每次选一条边权最大的边，如果把它加入答案不形成环，就把它加入答案。

推广一下，给定任意独立系统，任意给每个元素一个非负的权值，要求权值最大的独立集，容易得到下面的贪心算法:

1. 将元素按权值从大到小排序。
2. 按顺序依次考虑每个元素，如果把这个元素加入答案后仍然是一个独立集，就加入答案。

不幸的是，这个算法只有在特定条件下才会给出最优解。

比如考虑求二分图图的最大权值匹配，定义独立集为可以形成匹配的边集。考虑一个4个点3条边的图$V=\{u\_1, u\_2, u\_3, u\_4\}, w(u\_1,u\_2)=w(u\_3, u\_4)=5, w(u\_1, u\_4)=8, w(u\_2, u\_3) = 1$，贪心算法会选择边$(u\_1, u\_4), (u\_2, u\_3)$，权值是9，最优解是$(u\_1, u\_2), (u\_3,u\_4)$，权值是10。

我们把贪心算法能够使用的独立集系统称为拟阵(matroid)，比如上面定义在无向图边集上的独立集系统(一个边集是独立集当且仅当不包含环)，贪心算法实际上就是kruskal算法，为了方便，给它一个名字叫图拟阵(graphic matroid)。

特别地，很多问题只要求取一个最大的独立集，即元素权重都是单位1的特殊情况，如果这个独立集系统是拟阵，我们称这种拟阵叫做unweighted matroid。

拟阵的性质

那么如何判定一个独立集系统$M$是不是拟阵呢？下面三条定义是等价的:

1. $M$是拟阵，任意给元素分配非负的权值，贪心算法能得到最优解。
2. 假设有2个独立集$I\_1, I\_2, |I\_2| = |I\_1|+1$，那么$\exists e \in I_1 - I_2, I_1 \cup e \in \mathcal{I}$。 通俗地讲，就是如果2个独立集大小相差1，那么一定可以从大的独立集那里拿一个给小的，使新的集合还是独立集。
3. 若$A \subseteq E$，$I\_1, I\_2 \subseteq A$是$A$上的极大独立集，那么$|I\_1|=|I\_2|$。也就是$E$的任意子集上的极大独立集大小相同。

接下来引入几个概念:

1. 秩(Rank)：根据上面第3条，$E$的任意子集$A$上的极大独立集大小相等。这个大小就是$A$的秩，记为$r(A)$。
2. 基(Basis)：$A$的基上的任意极大独立集称为$A$的基。
3. 回路(Circuit)：极小的非独立集（相关集），即它本身不是独立集，但删掉任意一个元素后都是独立集。

为了方便理解，我们以图拟阵为例子.
图拟阵中任意边集$A \subseteq E$，$r(A)$是其生成子图的生成森林边数, 基就是任意生成森林，回路就是一个简单环。

再看一个独立集系统，它的元素集合是一些维数相同的向量，独立集的定义就是线性无关的向量集合。根据线性代数的知识，任意向量集合的极大线性无关组大小相同，即满足上面的判断独立集是否是拟阵的第3条，所以该独立集系统是一个拟阵，之后我们称它为线性拟阵。
线性拟阵的秩，基都和线性代数中吻合，回路就是极小的线性相关组。

为了后面证明的方便，再引入一个概念：

4. 闭包(closure)：$cl(A)=\lbrace e|r(A+e)=r(A)\rbrace$。

闭包的性质：若$e \in cl(A)$，则$cl(A) = cl(A+e)$，也就是说，$cl(A)=cl(cl(A))$。

拟阵交

问题定义

有两个拟阵$M\_1=(E,\mathcal{I}\_1),M\_2=(E,\mathcal{I}\_2)$，求$I \in \mathcal{I}\_1 \cap \mathcal{I}\_2$且使得$|I|$尽量大。

注意这里的$\mathcal{I}\_1,\mathcal{I}\_2$是“集合的集合”，$I$是“集合”。

算法感性认识

类比二分图最大匹配

许多时候，一个组合优化问题并不能表示成一个拟阵，但是却可以表示成两个拟阵甚至更多拟阵的交。比如二分图匹配，之前我们已经举了一个反例说明它虽然是个独立集系统，但并不是一个拟阵。然而，我们可以把它表示成两个拟阵的交:

我们用$G(L,R,E)$表示一个二分图，$L,R$分别是两边的顶点集合，$E$是边集，也是拟阵的基本元素集合。

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$中边的左端点互不相同。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$中边的右端点互不相同。

$M\_1,M\_2$是拟阵这一点可以自行验证。那么$I \in \mathcal{I}\_1 \cap \mathcal{I}\_2$且$|I|$尽量大的$I$就是二分图的一组最大匹配。

然后回忆匈牙利算法的过程，实际上就是找增广路。假设我们是从左边的点出发找到了增广路，设这条路的边为$e\_1,e\_2,\cdots,e\_{2k},e\_{2k+1}$（下标为偶数的边是之前的一些匹配边），之前的整个匹配边集为$I$，那么$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1}$是新的一个匹配边集。

我们从拟阵的角度来看这个过程，$I+e\_1$仍然是拟阵$M\_1$的独立集，即$I+e\_1 \in \mathcal{I}\_1$。但多了一条边之后，右边的某个点就会和$2$条边相关，右边的独立性被破坏。所以又变成$I+e\_1-e\_2 \in \mathcal{I}\_2$，又让右边满足独立，而且是去掉一个元素，左边肯定还是独立。

最终$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1}$在保持左边独立性的前提下让独立集大小增加1，而且右边也是独立的，于是就找到了一条增广路。

这个过程本质上是在奇数步尝试增加一个元素，并且保持$M\_1$的独立性，然而这可能会导致$M\_2$的独立性被破坏，所以在偶数步又去掉一个元素，使得重新满足$M\_2$中的独立性，直到在某个奇数步能找到一个元素，使得加上这个元素也不会破坏右边的独立性。我们也尝试把这种方法应用在一般的拟阵交问题上。

但是有一个问题，用上面的方法找增广路，在第$i$步找一个元素$e\_i$，它符不符合要求是和$e\_1,e\_2,\cdots,e\_{i-1}$的选择有关的，这样搜索空间就相当大了，所以我们需要把增广路的条件放宽一点，后面会证明放宽之后找到的解也一定是最优解。

考虑奇数步，原本的条件是$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1} \in \mathcal{I}\_1$，但是这个条件太难了，我们放宽成$I-e\_{2k}+e\_{2k+1} \in \mathcal{I}_1$。同理偶数步放宽成$I-e\_{2k}+e\_{2k-1} \in \mathcal{I}_2$。

算法流程

有两个拟阵$M\_1=(E,\mathcal{I}\_1),M\_2=(E,\mathcal{I}\_2)$，求交。

设目前得到的答案集合$I$，初始时$I$为空集。显然$I$是$E$的子集。

对$E$中每个元素建一个点，属于$I$的元素为左部，不属于的为右部，建成二分图。再另建源点$S$和汇点$T$。

• 如果$e \in E - I, I + e \in \mathcal{I}_1$，连边$(S,e)$。
• 如果$e \in E - I, I + e \in \mathcal{I}_2$，连边$(e,T)$。
• 如果$e\_x \in I, e\_y \in E - I, I - e\_x + e\_y \in \mathcal{I}_1 $，连边$(e\_x,e\_y)$。
• 如果$e\_x \in I, e\_y \in E - I, I - e\_x + e\_y \in \mathcal{I}_2 $，连边$(e\_y,e\_x)$。

然后对这个图求$S$到$T$的最短路，把最短路中在集合$I$中的元素从集合$I$中去掉，把最短路中不在集合$I$中的元素（$S$和$T$除外）加入集合$I$，进行下一次建图。

易知每次$I$的大小会增加$1$，算法在$S$到$T$不连通时终止，此时$I$就是答案。

令$r=\max(r(M\_1),r(M\_2)),n=|E|$，我们每次构建出来的图都是$n$个点，$rn$条边的图。由于增广次数不超过$r$，时间复杂度$O(r^2n)$。

算法正确性证明

正确性证明分为两个方面：

• 证明对于每一步增广得到的$I$，$I \in \mathcal{I}_1 \cap \mathcal{I}_2$。
• 证明不能再增广的时候得到的是大小最大的$I$。

一方面

对于这个问题，我们的证明思路是，设增广路上的左部点是$x\_1,\cdots,x\_n$，右部点是$y\_1,\cdots,y\_n,y\_{n+1}$。我们想证明的是$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$且$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_2$。

先证$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$，由于$y\_1$这个点是直接和$S$相连的，满足$I + y\_1 \in \mathcal{I}_1$，我们只需要证$I$和$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$具有相似的性质，以至于在$I + y\_1 \in \mathcal{I}_1$式中，可以直接把$I$替换为$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$。

具体来说，可以先证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$。假设我们已经证明了，由于增广路是最短路，所以$I+y\_i \notin \mathcal{I}_1 (i \ge 2)$，所以$r(I)=|I|=r(I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1})=r(I+y\_2+\cdots+y\_n+y\_{n+1})$（第三个等号成立是由于两个集合的闭包相等），又因为$I + y\_1 \in \mathcal{I}_1$，那么沿用拟阵上最优化问题的思路，相当于集合里面的元素为$I + y\_1$，加进去不形成环就往里加，最终所有的元素都能加进去。现在集合里面的元素增加了，变成$I+y\_1+\cdots+y\_n+y\_{n+1}$，在排序的时候把$y\_i$排到$x\_i$前面，加进去不形成环就往里加，最终加进去的元素集合就是$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1}$。

所以说剩下就是如何证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$。

对拟阵$M=(E,\mathcal{I})$定义交换图$D\_M(I)(I \in \mathcal{I})$。交换图是一个二分图，左部是$I$，右部是$E-I$，如果对于$x \in I,y \in E-I$，有$I-x+y \in \mathcal{I}$，那么就连无向边$(x,y)$。我们证明一个辅助证明的定理：

设$I \in \mathcal{I}$，$J$是一个大小等于$I$的由$E$中元素组成的集合，如果在$D\_M(I)$中存在唯一一个$I-J$到$J-I$的完美匹配，则$J \in \mathcal{I}$。

令$N$为完美匹配，把$N$中的边重定向，从$E-I$连向$I$，其余边从$I$连向$E-I$。由于匹配是唯一的，那么图中不存在环，所以可以拓扑排序，即可以把所有点重标号，使得边都是从标号小的指向标号大的。又因为从右部连回左部的边只有匹配大小这么多条，且是一一对应的连边，所以在处理右部连回左部的边时，我们给右部和左部的点相同大小的标号，那么这个图就有一个关键性质：左部点连向的右部点满足右部点的标号都不小于左部点的标号。

接下来使用反证法，设$J$不是独立集，那么$J$中必定存在环$C$，设$y\_i$是环中标号最大（且为$i$）的右部元素，由于之前的构造，对于环中其他的右部元素$y$，其匹配点$x\_i$到$y$是没有边的。没有边就说明$I-x\_i+y \notin \mathcal{I}$，也就是说$y \in cl(I-x\_i)$，即$C-y\_i \subset cl(I-x\_i)$。

两边同时取闭包$cl(C-y\_i) \subset cl(I-x\_i)$，因为$C$是环，所以$y\_i \in cl(C-y\_i)$，所以$y\_i \in cl(I-x\_i)$，但是这和$(x\_i,y\_i)$是交换图的匹配边矛盾。这样我们就证明了这个定理。

证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$，只需让$J=I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$，那么由最短路可知匹配是完美且唯一的，这样就证出来了。

证明另外一边$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_2$也是一样的，容易想到是利用$I+y\_{n+1} \in \mathcal{I}_2$，然后证明$I$和$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n$是差不多的东西。

另一部分

直接证Min-Max Formula。

$$\max\_{I \in \mathcal{I}}|I| = \min\_{U \subseteq E}{r\_1(U)+r\_2(E - U)}$$

首先容易证明$\forall I \in \mathcal{I}, \forall U \subseteq E, |I| \leq r\_1(U)+r\_2(E - U)$。

• 把$I$分成$A=I \cap U$和$B=I-A$两部分。
• $A \subseteq U, A \in \mathcal{I}\_1 \rightarrow r\_1(U) \geq |A|$
• $B \subseteq E - U, B \in \mathcal{I}\_2 \rightarrow r\_2(E - U) \geq |B|$

我们设$U$为交换图中可以到达$T$的点集。上面我们证了$r\_1(U) \geq |I \cap U|$。现在我们证$r\_1(U) \le |I \cap U|$。反证法，如果$r\_1(U) > |I \cap U|$，这就说明能到达$T$的点组成$M_1$的独立集的大小是要大于在交换图的左部且能到达$T$的点数，也就是说存在一个交换图中右部的点$y$，使得$I \cap U + y \in \mathcal{I}\_1$。有可能是$I + y \in \mathcal{I}\_1$，但这说明$S$要向$y$连边，而$y$又能到$T$，那么$S$和$T$依旧连通，矛盾。也有可能是存在一个$x \in I-U$，使得$I - x + y \in \mathcal{I}\_1$，但这说明$x$要向$y$连边，而$y$又能到$T$，那说明$x$也能到$T$，但$x \notin U$，也矛盾。对于$r\_2(E - U) \le |I - A|$的证明也类似，这里就不再重复。

综上，我们证明了算法结束的时候存在一个$U$，使得$|I|$能取到最大值，这就证明了算法的正确性。

推广

带权拟阵交

相当于每个元素有权值，求独立集的交，使得权值和最大。

依赖于拓展的Min-Max Formula。

实际的算法中，我们只要在交换图中定义点权，左部点（$x \in I$）的点权设为$-w(x)$，右部点（$y \in E-I$）的点权设为$w(y)$，求最短路的过程改为求一条从$S$到$T$的路径，第一关键字是点权最大，第二关键字是经过的边数最小即可。证明略。

多个拟阵交

由于拟阵的交不是拟阵，所以不能两两求交。可以把多个拟阵的交规约到哈密顿路问题上，从而证明多个拟阵的交是NP-hard的。证明略。

例题

二分图匹配

上面的分析就用的二分图匹配。这里略。

最小树形图

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$的边看作无向边时无环。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$的边每个点入度不超过一，特别地根入度为零。

Colorful Tree

给定带权无向图 $G(V, E)$ ，每条边拥有一个 $1$ 到 $n−1$ 中的颜色，求一个权最大的生成树，满足每种颜色只出现一次。

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$的边无环。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$的边每种颜色出现次数不超过一。