In mathematics you don't understand things, you just get used to them.

分类 笔记 下的文章

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$的任意子集上的极大独立集大小相同。


证明

links

接下来引入几个概念:

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

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

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

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

  1. 闭包(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)$。


感性理解连边

由于是把左部的点$e\_x$换成右部的点$e\_y$,所以都是$I - e\_x + e\_y$。

连边的方向可以先感性理解:有一种想法是就像上面说的一样,奇数步$\mathcal{I}\_1$,偶数步$\mathcal{I}_2$。还有一种想法是,因为连好之后是从$S$直接到右部点$e\_y$,$e\_y$相关的一条信息是$I + e\_y \in \mathcal{I}_1$,这个右部点接下来会向左走增广路,那么和这个右部点相关的另外一条信息就应该和$\mathcal{I}_2$有关了。

算法正确性证明

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

  • 证明对于每一步增广得到的$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$的边每种颜色出现次数不超过一。