组合数学基础

排列与组合

PE364 Comfortable distance

题意

有 $n$ 个人依次往 $n$ 个位置入座，每个人遵循相同的选择位置的规律：

1.先选两边没有人的位置

2.若不存在两边没有人的位置，则选只有一边有人的位置。

3.若不存在只有一边有人的位置，则选择两边均有人的位置。

$n \le 10^6$，求最后答案对 $10^9 + 7$ 取模的结果。

解法

先考虑一直放第一种情况，由于会有间隔 $\text{ 1,2 }$ 的情况，发现第一种情况的总人数是不确定的。

可以枚举放了 $p_2$ 个间隔为 $2$ 的人，设间隔为 $1$ 的人有 $p_1$ 个。

已知 $n$ 和 $p_2$ ，由于我们设的前提是极大的第一种情况，即必须放到不能放第一种情况为止，所以可以推出 $p_1$。

放完 $p_1$ 和 $p_2$ ，实际上是放了 $p_2 + p_1 + 1$ 个人，因为一定有一个人可以放在端点而不破坏间隔的性质。

在此时我们占下了 $3p_2+2p_1+1$ 个位置，仍然可能剩下 $h$ 个位置。我们在保证原有性质的同时，可以自由地分配空位的位置。发现这些位置只能被放在两端，且 $h \in \text{ \{0,1,2\} }$ ，两个空位不能被放在同一个端点。

可以通过枚举 $h$ 来确定 $p_1$。

$$p_1 = n - 3 p_2 - 1 - h$$

接着考虑最终对一组确定的 $p_1$ , $p_2$ , $h$ 所能贡献的答案。

由于3种情况的放置之间相互独立，考虑先分配 $p_1$ 和 $p_2$ 的排列方案数，即放完第一种情况的总方案数。

$$(p_1+p_2+1)!\times \binom{p_1+p_2}{p_1}$$

接着放完第二种情况，发现每一个 $p_2$ 都提供了个两种不同的决策，则放第二种情况的总方案数为：

$$2^{p_2}\times(p_2+h)!$$

在最后放第三种情况:

$$(p_1+p_2)!$$

所以最后的答案为：

$$\displaystyle \sum_{p_1,p_2,h}(p_1+p_2+1)!\times \binom{p_1+p_2}{p_1} \times 2^{p_2}\times(p_2+h)!\times (p_1+p_2)!$$

代码

MODint fac[N] , inv[N];

MODint C(int n , int m) {
  if (n < m) return 0;
  return fac[n] * inv[m] * inv[n - m]                
}

int main() {
  cin >> n;
  fac[0] = 1;
  for (int i = 1 ; i <= M ; i++) {
    fac[i] = fac[i - 1] * i;
  }
  inv[M] = fac[M].inverse();
  for (int i = M ; i >= 1 ; i--) {
    inv[i - 1] = inv[i] * i;
  }
  MODint ans = 0;
  for (int l0 = 0 ; l0 <= 1 ; l0++) {
    for (int r0 = 0 ; r0 <= 1 ; r0++) {
      for (int p2 = 0 ; p2 <= n / 3 ; p2++) {
        int d = (n - 3 * p2 - 1 - l0 - r0);
        if (d < 0) break;
        if (d % 2 == 1) continue ;
        int p1 = d / 2;
        ans += fac[p1 + p2 + 1] * C(p1 + p2 , p2) * pow(2 , p2) * fac[p2 + l0 + r0] * fac[p2 + p1]; 
      }
    }
  }
  cout << ans << endl;
  return 0;
}

AGC 001 - BBQ Hard

题意

计算：

$$\displaystyle\sum_{i=1}^n\sum_{j=i+1}^n\binom{a_i+a_j+b_i+b_j}{a_i+a_j}$$

$n\le 10^6$ , $1\le a_i,b_i\le 2000$

解法

看到 $a_i$ 的值域，能够联想到一个很自然的平方递推

$$f_{i,j}=f_{i-1,j}+f_{i,j-1}$$

令 $f_{0,0}=1$ 发现从 $(0 , 0)$ 到 $(n , m)$ 的路径条数 $\binom{n+m}{n}$ 恰等于 $f_{n,m}$。

对于这题有一个巧妙的转换：令每一个 $f_{-a_i,-b_i}=1$ ，则求得的 任意 $f_{a_i,b_i}$ 有：

$$f_{a_i,b_i}=\displaystyle\sum_{j=1}^{n}\binom{a_i+a_j+b_i+b_j}{a_i+a_j}$$

所以原式等于：

$$\displaystyle\frac{\sum_{i=1}^{n} f_{a_i,b_i}}{2} - \displaystyle\sum_{i=1}^{n} \binom{2a_i+2b_i}{2a_i}$$

代码

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n;    
    for (int i = 0 ; i < n ; i++) {
        cin >> A[i] >> B[i];
        f[dt - A[i]][dt - B[i]] += 1;
    }
    for (int i = -2000 ; i <= 2000 ; i++) {
        for (int j = -2000 ; j <= 2000 ; j++) {
            int x = dt + i;
            int y = dt + j; 
            f[x][y] += f[x - 1][y] + f[x][y - 1];
        }
    } 
    MODint ans = 0;
    for (int i = 0 ; i < n ; i++) {
        ans += f[dt + A[i]][dt + B[i]];
        ans -= C(2 * (A[i] + B[i]) , 2 * A[i]);
    }
    cout << ans / 2 << endl;
    return 0;
}

AGE002 F - Leftmost Ball F

题意

有总计 $n\times k$ 个位置，有 $n$ 种颜色的球，各 $k-1$ 个，还有 $n$ 个白球。第 $i$ 种新出现的球能被放下，当且仅当已经放下至少 $i$ 个白球。

求所有局面的方案数对 $10^9+7$ 取模的结果。 $n,k\le 2000$

解法

首先固定选择颜色的顺序，这样的好处就是我们只需要在最后对答案乘上一个 $n!$ 的贡献，而在途中不需要考虑颜色的情况。

设 $f_{i,j}$ 表示放了 $i$ 个白球，且已放完 $j$ 种颜色。

每一次放白球我们保证把白球放在最前面的能放的位置，这样可以保证后面的球一定合法且不重复。

同样的，每次放入一种新颜色的球之后先要将一个球放在最前面的合法的位置，这样的目的也是为了保证不重复计算 $1,2$ 和 $2,1$ 这种情况。

我们可以得到以下式子：

$$f_{i,j}=f_{i-1,j}+\text{[j > 0]} \times f_{i,j-1}\times \binom{n \times k - 1 - i - (j-1)\times(k-1)}{k-2}$$

代码

int main() {
    cin >> n >> k;
    if (k == 1) {
        cout << "1\n";
        return 0;
    }
    f[0][0] = 1 , len = n * k;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j <= i ; j++) {
            f[i][j] = f[i - 1][j];
            if (j != 0) {
                f[i][j] += f[i][j - 1] * C(len - i - (k - 1) * (j - 1) - 1 , k - 2);
            }
        }
    }
    cout << f[n][n] * C.fac[n] << endl;
    return 0;
}

CERC 2015 F Frightful Formula

题意

给出一个 $n\times n$ 大小矩阵的第一行 $\{l_n\}$ 和 第一列 $\{t_n\}$。

以及其他位置的递推公式:

$$f_{i,j}=a\times f_{i-1,j} + b\times f_{i,j-1} + c$$

求出 $f_{n,n}$ 在模 $10^6+3$ 下的值。 $n\le 200000$

解法

第一行，第一列的值是无用的。因为存在 $f_{1,2}$ 和 $f_{2,1}$ 覆盖了所有 $f_{1,1}$ 的转移。

先考虑第一行和第一列对最终答案的贡献：

$$\begin{aligned} \sum_{i=2}^{n}\binom{2 n-1-i}{n-i}a^{n-i}b^{n-1}\times t_i \\ \sum_{i=2}^{n}\binom{2 n-1-i}{n-1}a^{n-1}b^{n-i}\times l_i \end{aligned}$$

接着再考虑一个 每一个 $f_{i,j}$ 中 $c$ 对转移所产生的的贡献：

$$\sum_{i=2}^{n}\sum_{j=2}^{n}\binom{2n - i - j}{n - i}a^{n-i}b^{n-j}\times c$$

把组合数化开:

$$\sum_{i=2}^{n}\sum_{j=2}^{n}\frac{(2n - i - j)!}{(n-i)!\times(n-j)!}\times a^{n-i}b^{n-j} \times c$$

推出来一个卷积的形式，于是就可以用任意模数MTT做了。

$$c\times \sum_{s=0}^{2\times n - 4} s! \sum_{i=0}^{s}\frac{a^i}{i!}\times \frac{b^{s-i}}{(s-i)!}$$

但是这个模数并不是一个正经模数。

可以考虑对这个式子进行递推：

$$\begin{aligned} f_n &= \sum_{i=0}^{n}\sum_{j=0}^{n} \binom{i + j}{i} a^ib^j \\ &= \sum_{i=0}^n a^i\sum_{j=0}^n \binom{i + j}{i} b^j \end{aligned}$$

提出关于 $n$ 的项：

$$f_n = \sum_{i=0}^{n-1} a^i\sum_{j=0}^{n-1} \binom{i + j}{i} b^j+a^n\sum_{i=0}^n\binom{n+i}{n}b^i+b^n\sum_{i=0}^n\binom{n+i}{n}a^i-\binom{2n}{n}a^nb^n$$

令 $u_n = \sum_{i=0}^n\binom{n+i}{n}b^i$ , $v_n=\sum_{i=0}^n\binom{n+i}{n}a^i$。

$$f_n = f_{n-1} + a^nu_n+b^nv_n-\binom{2n}{n}a^nb^n$$

考虑到 $u_n$ 和 $v_n$ 形式相同，只需考虑 $u_n$ 的递推：

$$\begin{aligned} u_n &= \sum_{i=0}^n\binom{n+i}{n}b^i\\ &= \sum_{i=0}^n\left(\binom{n-1+i}{n-1}+\binom{n+i-1}{n}\right)b^i\\ &\text{(注意到右边项当 i=0 时无意义)} \\ &=u_{n-1}+\binom{2n-1}{n-1}b^n+b\sum_{i=0}^{n-1}\binom{n+i}{n}b^i\\ &=u_{n-1}+\binom{2n-1}{n-1}b^n+b\times u_{n}-\binom{2n}{n}b^{n+1}\\ \end{aligned}$$

移项整理得:

$$\begin{aligned} (1-b)u_n&=u_{n-1}+\binom{2n-1}{n}b^n-\binom{2n}{n}b^{n+1} \\ u_n&=\frac{1}{1-b}\times\left(u_{n-1}+\binom{2n-1}{n}b^n-\binom{2n}{n}b^{n+1}\right) \end{aligned}$$

若 $a=1$ 或 $b=1$，带回原式则有：

$$\begin{aligned} u_{n-1}&=\binom{2n}{n}-\binom{2n-1}{n}\\ &=\binom{2n-1}{n-1} \end{aligned}$$

则有 $u_{n}=\binom{2n+1}{n}$。我们最后只需求出 $f_{n-2}$ 即为最终答案。

解法2

观察递推式子

$$f_{i,j}=a\times f_{i-1,j}+ b\times f_{i,j-1} + c$$

类似中学数列的递推形式，可以设一个变量 $x$ ，令 $g_{i,j}=f_{i,j}+x$，同时满足：

$$g_{i,j}=a\times g_{i-1,j} + b\times g_{i,j-1}$$

即消除常数项的影响。
通过计算可以得到：

$$x=\frac{c}{1-a-b}$$

发现 分母可能为 0 ，即 $a=0,b=1$ 或 $a=1,b=0$。
看起来好像只要 $O\left(n\right)$ 递推就可以了。(口胡的，可能有点问题)

Ramsey 定理

对任意正整数 ${\displaystyle k}$ 和 ${\displaystyle l}$ ，若一个聚会的人数 ${\displaystyle n}$ 足够大，则无论相识关系如何，必定有${\displaystyle k}$ 个人相识或 ${\displaystyle l}$ 个人互不相识。给定 ${\displaystyle k,l}$ 时，保证前述结论的最小 ${\displaystyle n}$ 值称为拉姆齐数 ${\displaystyle R(k,l)}$ ，其值取决于 ${\displaystyle k,l}$ 。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的 ${\displaystyle k}$ 阶完全图或蓝色的 ${\displaystyle l}$ 阶完全图。

拉姆齐定理是鸽巢定理在图上的一个拓展。

重要性质

$R(n,m)=R(m,n)$ , $R(1, m) = 1$ , $R(2, m) = m$ , $R(3, 3) = 6$

$R(n, m) \le R(n − 1, m) + R(n, m − 1)$

CCPC 长春 2016 G Instability

在一个有 $n$ 个点 和 $m$ 条边组成的无向图上，如果一个点集诱导的子图中存在点数至少为 $3$ 的团或独立集，那么认为这个点集是 不稳定的，问有多少点集是不稳定的，答案对 $10^9 + 7$ 取模

$3\le n\le 50$ , $0\le m \le \frac{n\times(n-1)}{2}$

解法

由 $R(3,3)=6$ 可得，对于一个集合 $S$ 若 $\text{size }S \ge 6$ ，则 $S$ 一定是不稳定的。

对于 $\text{size }S\le 2$ 的情况，则 $S$ 一定是稳定的。

所以只需对 $\text{size }S=\{3,4,5\}$ 的情况爆搜即可。

复杂度 $\displaystyle O(\binom{n}{3}+\binom{n}{4}+\binom{n}{5})$

容斥原理

51nod 1667 概率好题

题意

甲乙进行比赛。

他们各有 $k_1$ , $k_2$ 个整数集合 $[L_i,R_i]$

每次等概率随机从他们拥有的每个集合中都取出一个数 $x_i \in [L_i,R_i]$

$$S_1=\displaystyle\sum_{i=1}^{k_1} x_i\;,\;S_2=\displaystyle\sum_{i=k_1+1}^{k_1+k2}x_i$$

求 $S_1\gt S_2$ , $S1=S_2$ , $S_1\lt S_2$ 的概率在模 $10^9+7$ 意义下的值。

解法

首先对式子做变形，首先考虑 $S_1\lt S_2$ 的情况，其余情况类似。

$$\begin{aligned} \because&\;\;S_1\;\lt S_2 \\ \therefore&\;\sum_{i=1}^{k_1} x_i \lt \sum_{i=k_1+1}^{k_1+k_2} x_i\\ \text{(平移变量 } x_i&\text{ 使其均从 0 开始 并小于等于一个上限 } l_i\;)\\ \because&\;\sum_{i=1}^{k_1+1}(L_i+x_i)-\sum_{i=k_1+1}^{k_1+k_2}(R_i-x_i)\lt0 \\ \therefore&\;\forall i\in [1,k_1+k_2]\; , \;x_i\le R_i-L_i\\ \end{aligned}$$

设 $t = \sum_{i=k_1+1}^{k_1+k_2}R_i-\sum_{i=1}^{k_1}L_i-1$ 移项可得：

$$\begin{aligned} \sum_{i=1}^{k_1+k_2}x_i \lt \sum_{i=k_1+1}^{k_1+k_2}R_i-\sum_{i=1}^{k_1}L_i=t+1\\ \end{aligned}$$

即求解：$\sum_{i=1}^{k_1+k_2} x_i \le t$ 的解的组数。

考虑等号的情况有一个经典的隔板法 $\text{ans } =\binom{t+k_1+k_2-1}{k_1+k_2-1}$ 的解法。

关于如何处理不等号，可以加入一个无限制的自由变量 $x_{k_1+k_2}$。

考虑上限如何用容斥处理，每次枚举 $k$ 个变量超过上限，限定这 $k$ 个变量恰好等于 $R_i-L_i+1$，这样这些变量就变成无限制的变量了。

代码

Combine<233 , MOD> C;

MODint Ans0 = 0 , Ans1 = 0;

void dfs(int cur , int flag , int64 sum , const vector<int> &arr) {
  if (cur == arr.size()) {
    Ans0 += flag * C(sum + cur - 1 , cur);
    Ans1 += flag * C(sum + cur - 1 , cur - 1);
    return ;
  }
    dfs(cur + 1 , flag * -1 , sum - arr[cur] , arr);
    dfs(cur + 1 , flag , sum , arr);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) {
    int n , m;
    int64 sum = 0;
    cin >> n;
    vector<pair<int, int>> A(n);
    vector<int> p;
    MODint d = 1;
    for (auto &x : A) {
      auto [l , r] = x;
      cin >> l >> r;
      d *= (r - l + 1);
      sum += r;
      p.push_back(r - l + 1);
    }
    cin >> m;
    vector<pair<int, int>> B(m);        
    for (auto &x : B) {
      auto [l , r] = x;
      cin >> l >> r;
      d *= (r - l + 1);
      sum -= l;
      p.push_back(r - l + 1);
    }
    Ans0 = Ans1 = 0;
    dfs(0 , 1 , sum , p);
    Ans0 /= d , Ans1 /= d;
    MODint Ans2 = 1 - Ans0 - Ans1;
    cout << Ans0 << ' ' << Ans1 << ' ' << Ans2 << endl;
  }
  return 0;
}

XVI Open Cup, Grand Prix of Ukraine J Joining Powers

题意

定义 $S(k)=\{1^k,2^k,3^k,\;...\;,n^k,\;...\;\}$ ， 有 $q$ 次询问，每次询问 $m$ 个集合的并集 $\bigcup_{i=1}^{m} S\left(k_i\right)$ 中第 $N$ 小的元素，保证答案不超过 $10^{17}$。

$$1\le q \le 10^4,1\le m \le 42,1\le k_i\le50,1\le N\le10^9$$

解法

第 $N$ 小的元素可以二分出来，接下来分析如何完成二分。

设二分出来的值是 $x$ ，考虑如果 $m=1$，可以求得集合中有 $\lfloor x^{1/k}\rfloor$ 个小于 $x$ 的值。

对于多个集合的情况可以考虑容斥，对于枚举的 $t$ 个集合，记 $\text{lcm }\{k_{i_1},k_{i_2},\;...\;,k_{i_t}\}=v$ ，对这些集合求交即为 $S(v)$。对于二分出来的值的实际 $\text{rank}$ 值，是集合的并，我们可以用集合的交进行容斥。

由于答案不超过 $10^{17}$，不难发现 当 $v\ge 64$ 时，仅有 1 元素是有价值的。

于是我们便可以对给定的 $k_i$ ，在有限的值域内求出所有可能的 $v$ 的容斥系数。

SPOJ RNG - Random Number Generator

给定 $n$ 个整数 $x_i$，以及两个数 $a$ 和 $b$。随机生成 $n$ 个范围在 $[-x_i,x_i]$ 内的实数，求生成的随机数的和在 $[a,b]$ 间的概率.

$$n\le10$$

解法

考虑无限制情况怎么做: 对于 $n$ 维的情况，我们可以设一个极大的上限 $s$ 记为所有上限的总和, 方案数就会是：

$$\int_{0}^{s} \dots \int_{0}^{s} 1 \text{dx}_1\dots\text{dx}_n=\frac{s^n}{n!}$$

将变量的范围平移到 $[0,2x_i]$ ， 枚举多少个数超过上限 , 剩下所有数套用上面公式即可。

AGC 005 D ∼K Perm Counting

给定 $n$ 和 $K$ ，求有多少排列满足 $\forall i \in \{1,2,\dots,n\} , |a_i-i|\neq K$

解法

首先考虑容斥，设 $f(x)$ 为恰好有 $x$ 个位置满足 $|a_i-i|=k$，则答案即为：

$$\sum_{i=0}^n (-1)^i\times f(i)\times(n-i)!$$

考虑如何求 $f(x)$ 。首先建立一个二分图，左侧的点表示下标，右侧的点表示值，存在一条边 $(l_i,r_i)$ 当且仅当 $l_i-r_i=k$ 时。

实际上我们可以把点按取模 $k$ 的值分成总共 $k$ 种链，每种链各两条。

每条链之间独立，于是我们可以将问题转化为：在一条链上选取 $x$ 条不相交的边有多少种方案。

考虑一个简单的 $O(n^2)\text{ dp}$ 做法，记 $dp_{i,j,0/1}$ 为前 $i$ 个点，选取了 $j$ 条边，与 $i$ 这个点相连的向前的边或者不选的方案数。

$$\begin{aligned} dp_{i,j,0} &= dp_{i-1,j,0} + dp_{i - 1,j,1}\\ dp_{i,j,1} &= dp_{i-1,j-1,0} \end{aligned}$$

注意链与链之间答案的继承即可。

解法二

发现瓶颈在于统计 $f(x)$。对于单条链的答案怎么处理，设链长为 $l$, 由于链首一定不能选，可以考虑捆绑两个点，然后用组合数计算：

$$f(x)=\binom{l-x}{x}$$

如何处理链和链之间答案的合并呢，发现转移是一个卷积形式。再之后，由于将链按模 $k$ 的值分类后，链长 $l$ 只有两种情况即：

$$l\in \{\frac{n}{k},\frac{n}{k}+1\}$$

对两种链长构造出他们的 OGF $F(x)$ , $G(x)$ 之后，记分别有 $s_1$ 和 $s_2$ 条链，则答案的 OGF 则为：

$$F^{s_1}(x)\times G^{s_2}(x)$$

用 NTT 就可以 $O(n\log n)$ 了。