n 个小球放入 r 个盒子

小球 盒子 空盒 方案数
相异 相异 允许 $r^n$
相异 相同 不允许 $S_2(n,r)$
相异 相异 不允许 $r! \ S_2(n,r)$
相异 相同 允许 $\sum_{k=1}^r S_2(n,k)$
相同 相异 允许 $C_{n+r-1}^n$
相同 相异 不允许 $C_{n-1}^{r-1}$
相同 相同 不允许 $P_r(n)$
相同 相同 允许 $P_r(n+r)$

从上至下编号 1~8 的话,1 最简单,2 是第二类  Stirling 数,2 继而推出 3、4。5 和 6 用插板法可以推出,7 和 8 是整数拆分问题。

第 1 种:$n$ 个球,每个球都有 $r$ 种不同的选择。

第 2 种:$n$ 个相异的小球放入 $r$ 个相同的盒子,不允许空盒,记为 $S(n, r)$。 $S(n, r)$ 可以递归的计算。其中:

  • $S(n, n) = S(n, 1) = 1$
  • $S(n, r) = S(n - 1, r - 1) + r \times S(n - 1, r)$

分两种情况考虑,第一种是 $a$ 这个元素独占一盒($S(n - 1, r - 1)$),第二种是 $a$ 选择某一盒(此时每盒都不同,$r$ 个选择)($r \times S(n - 1, r)$)。

另外,Bell 数 $B_n = \sum_{k=1}^n S(n,k)$ 。

第 3 种:相当于先进行第 2 种之后,再对所有的盒子做全排列。

第 4 种:枚举有几个空盒。

第 5 种:在 $(n + r - 1)$ 个位置中,选出 $n$ 个作为小球,剩下的位置自然变成盒子的边界。

第 6 种:在 $(n - 1)$ 个位置中,选出 $(r - 1)$ 个作为盒子的边界。

第 7 种:就是正整数 $n$ 的 $r$ 划分。而 $P_k(n)=P_{k-1}(n-1)+P_k(n-k)$ (分是否包含整数 $1$ 来讨论)。

第 8 种:允许空集合,那么相当于把每个集合都先加 $1$,然后再做不允许空集合的划分。

Some Math Formulas

Matrix Norm

$\forall v \in \mathbb C^n$,

$\forall A \in \mathbb C^{m \times n}$,

Power mod

Mobius Transfermation

图论概念整理

匹配其实也就是边独立集。

  • 边独立集 := 边集的子集,任意两边没有公共端点
  • 边覆盖 := 边集的子集,覆盖了原图的所有点(原图中每一个点,都是这个边集中的某边的端点)

类似的有点独立集和点覆盖:

  • 点独立集 := 点集的子集,任意两点没有相连的边
  • 点覆盖 := 点集的子集,覆盖了原图的所有边(原图中每一条边,至少都有一个端点属于这个集合)

题目中涉及到的概念一般是:最大边独立集(最大匹配),最小边覆盖,最大点独立集,最小点覆盖。

他们存在这些关系:

  • 在没有孤立点的图中,$\lvert 最大边独立集\rvert + \lvert 最小边覆盖\rvert = \lvert V\rvert$
  • 一般图中,$\lvert 最大点独立集\rvert + \lvert 最小点覆盖\rvert = \lvert V\rvert$

一般图的最大边独立集可以使用 Tutte 矩阵来计算。一般图的最大点独立集是 NP-hard 的。

二分图中,最大边独立集可以使用匈牙利算法计算,而 $\lvert 最小点覆盖 \rvert = \lvert 最大边独立集 \rvert$,于是在一般图中 NP-hard 的最大点独立集问题,在二分图中也有多项式算法了。

补充

如果图中点和边有权值,相应的也有一些定理:

  • 一般图中,最大点权独立集的权值和 + 最小点权覆盖的权值和 = 所有点权值和

可惜现在还没有发现最小边权覆盖和最大边权独立集之间的关系。

二分图的最小点权覆盖的解法如下:

最小点权覆盖即选出一个点集 $V$,使得原图中的边 $<u, v>$,$u \in V, v \in V$ 至少有一个成立,同时最小化点集 $V$ 的权值之和。

那么考虑如下最小割建图:

  1. 增加源点 $s$,汇点 $t$,从 $s$ 连边到 $X$ 部中的点 $x$,权值为 $x$ 的权值;
  2. 从 $Y$ 部中的点 $y$ 连边到 $t$,权值为 $y$ 的权值;
  3. 对原图中的所有边 $<u, v>$,从 $u$ 连边到 $v$,权值为 $\infty$。

这样建图后考虑最小割,$<s, u>$ 和 $<v, t>$ 至少有一个在最小割中,因为 $<u, v>$ 权值为 $\infty$,一定不会出现在最小割中。这正好与 “$u \in V, v \in V$ 至少有一个成立” 形式相符。

支持快速删除和“随机访问”的数据结构

这里所谓的快速,其实只是要求复杂度在 $\mathcal O(n)$ 以下,比如常见的 $\mathcal O(\sqrt n)$ 和更常见的 $\mathcal O(\log n)$、$\mathcal O(\log^2 n)$ 等等。“随机访问”也是要求这个复杂度。

显然平衡树是可以轻松达到这个要求的。比如 Treap 实现的名次树,两项操作的复杂度都是 $\mathcal O(\log n)$,而且它还支持 $\mathcal O(\log n)$ 的插入新元素 - - 。

不过我这里要介绍的是一个更加轻量级的数据结构:BIT(树状数组)。

用 BIT 维护一个数组,数组的值为 $1$,表示当前位置有元素,值为 $0$,表示元素被删掉。那怎么找到真实数组的第 $k$ 个元素(从零开始计数)呢?其实也就是找到最小的 $i$,使得 $sum[0, i] > k$。显然这个可以二分,再加上 BIT 的复杂度,一次随机访问的复杂度就是 $\mathcal O(\log^2 n)$。因为 BIT 的 $\mathcal O(\log n)$ 常数非常小,这个复杂度还算能忍受。

但是,我要介绍一个更快的方法。就是下面的 get 函数:

class BIT {
    int[] vs;

    BIT(int n) {
        vs = new int[n + 1];
    }

    void add(int k, int a) {
        for (int i = k + 1; i < vs.length; i += i & -i) {
            vs[i] += a;
        }
    }

    int sum(int s, int t) {
        if (s > 0) return sum(0, t) - sum(0, s);
        int res = 0;
        for (int i = t; i > 0; i -= i & -i) {
            res += vs[i];
        }
        return res;
    }

    //min(i) for sum[0, i] > k
    int get(int k) {
        int p = Integer.highestOneBit(vs.length - 1);
        for (int q = p; q > 0; q >>= 1, p |= q) {
            if (p >= vs.length || k < vs[p]) p ^= q;
            else k -= vs[p];
        }
        return p;
    }
}

这就是一个普通的树状数组里的一个函数,以前在一些其他地方的模板上也看到过,我这个是在东大模板上抄下来的。

他可以在 $\mathcal O(\log n)$ 的复杂度实现我们的需求,不过他的正确性证明我就不深究了 - - 我看到一个异或的运算就已经吓跑了 - - 。

一类区间贪心问题的简单解法

注意这里说的简单,并不是代码行数少,或者复杂度低,而是,思路清晰,容易实现(虽然行数更多)。

区间贪心问题现在见过这几种:

  • 区间选点:给定许多区间,然后让你选最少的点,使得每个区间至少有一个点覆盖。
  • 最少区间覆盖:给定许多区间,然后再给你一个大区间,问你,覆盖这个大区间,至少需要几个给定的区间?
  • 最多独立区间:给定许多区间,让你选出最多的区间,要求他们互不接触。

这三类问题看似不容易,但是如果给定一个条件:所有的区间互不包含,那么就变得异常简单了。 可以把他们按随便一个端点从左到右排序,然后排序出来的效果就是这样的:

-----
  -----
    -----
            ----

然后试着去思考上面的三个问题,发现都很简单。

然后,我们又发现对于相互包含的区间,见下面:

---------
  ----

其实都可以只留下一个区间,一问题和三问题要小区间,二问题要大区间。那么我们可以简单地是掉这些相互包含区间吗?如果可以,问题就简化成简单的无包含区间的贪心问题了。

现在我们考虑如何去掉相互包含的区间。一个简单的想法是,对于每个区间,看它是否被别的区间包含,那么这是 $\mathcal O(n^2)$ 的算法,对于之前的经典 $\mathcal O(n \log n)$ 的解法来说,显然不够优秀。那么有没有复杂度更低的去包含区间的方法呢?

有的:我们考虑让可能相互包含的区间,排序后紧挨在一起,那么就可以在排序后在线性时间内去包含区间了。具体的排序方法是,如果你想要小区间,那么优先按右端点从小到大,然后按左端点从大到小排序,如果你想要大区间,那么优先按左端点从小到大,然后按右端点从大到小排序。

之后就比较简单了,举一个要小区间的例子:

List<P> getShorter(P[] ps) {
    Arrays.sort(ps); // 优先按右端点从小到大,然后按左端点从大到小排序。
    List<P> shorter = new ArrayList<P>();
    int n = ps.length;
    for (int i = 0; i < n; ) {
        P p = ps[i++];
        shorter.add(p);
        while (i < n && ps[i].x <= p.x) i++;
    }
    return shorter;
}

看,去包含是不是很简单 :)