「笔记」一些组合题

来自qrsikno的课件

AGC002F Leftmost Ball

Description

给定 $n$ 种颜色, 每种颜色有 $k$ 个球.

现在把他们排列成一行, 再把每种颜色第一个染成 0 号颜色 (之前未出现).

求经过操作之后能有多少种不同的序列.

两个序列不同被认为是长度不同或某个位置颜色不同.

$n \le 2000, k \le 2000$

Solution

[动态规划] [计数] [组合数学]

因为颜色等价，可以忽略颜色的排列顺序，最后乘上$k!$

$0$和其他颜色放一起填，需要保证任意前缀都有$num_0 \ge num_{color}$

$dp[i][j]$表示当前填了$i$个$0$，$j$种颜色的方案数，每次把一种颜色全部加进来

$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\times \binom{nk - i - (j - 1)(k - 1) - 1}{k - 2}$

$dp[i - 1][j]$的系数为$1$是因为必须钦定$0$放在当前第一个空位，否则会算重

组合数上面最后一项$-1$同理，钦定第一个数填在第一个空位上

下面$-2$是要减去$0$和当前颜色的第一个数

Luogu P1758 管道取珠

Solution

[计数]

$\sum a_i ^ 2$可以看成两个完全一样的游戏同时进行，它们得到了相同的串的方案数

设$dp[i][j][k][l]$表示第一个游戏进行到$(i, j)$，第二个进行到$(k, l)$的方案数

显然$l = i + j - k$，复杂度$O(n^3)$

CF1111D Destory the Colony

Description

给定一个偶数长度 $n(n \le 10^5 )$ 的字符串, 只包含大小写字母.

有 $q(q \le 10^5 )$ 次询问, 每次指定两个位置, 要求通过交换字符, 使这两个位置上的类型的字符在字符串中线同一边(要么全在左半边，要么全在右半边).

并且对于其他类型的字符, 不能跨过串的中线 (也就是说必须在一边, 但是可以不跟指定的字符一边).

询问之间独立, 求方案数模 $10^9 + 7$ 的值

Solution

[动态规划] [退背包]

先不考虑指定的两个位置的限制

枚举$S$表示放在左半边的字符的集合

根据可重排列计数，$S$的答案就是：

$\frac{(\frac{n}{2}!)^2}{\prod_{i\in {S}}cnt_i * \prod_{i\notin {S}}cnt_i} = \frac{(\frac{n}{2}!)^2}{\prod_i cnt_i}$

发现与$S$具体是什么无关

因为有$|S| = \frac{n}{2}$，所以需要做一次背包求出方案数，再乘上面那个东西就是答案

---

然后考虑指定了位置$(i, j)$怎么做

可能的$(i, j)$很少，可以把答案都预处理

显然，只需要把$i$和$j$在背包中挖掉即可

for (int k = Cnt[i]; k <= N / 2; ++k)
    Add (f[k], Mod - f[k - Cnt[i]]);

并且答案要乘$2$，因为$i$和$j$可以同时在左半边或者右半边

CF785D Anton and School 2

Description

[范德蒙德卷积]

Solution

a