「做题记录」组合计数选做

· · 算法·理论

写的是主要难点在组合数学上的题。计数 DP 做题记录。

被 employ 和 sale 创飞后发现基础不牢,因此放置了一定量的水题(

ARC180A ABA and BAB

给出一个字符集为 \{\tt{A},\tt{B}\} 的字符串 S,长度为 n。你可以任意次地执行如下操作:将子串 \tt{ABA} 替换为 \tt{A},或者将子串 \tt{BAB} 替换为 \tt{B}。

求出经过操作后,可以得到的本质不同字符串数目。对 10^9+7 取模。

:::::success[题解] 注意到对于一个形如 \tt{ABABA\cdots} 的极长连续段,其操作后形态不变,且长度减去 2。分别求出每个连续段,则长为 k 的段贡献为 \lceil \frac{k}{2} \rceil,乘法原理合并。

复杂度 O(n)。

:::::info[代码]

const int N = 2.5e5 + 5;
int n;
char s[N];
void _main() {
    cin >> n >> (s + 1);
    int cur = 0;
    mint res = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i] != s[i - 1]) cur++;
        else res *= (cur + 1) / 2, cur = 1;
    } res *= (cur + 1) / 2, cout << res;
}

:::::

P11250 [GESP202409 八级] 手套配对

有 n 对手套,每只手套有标号,求从中取出 m 只手套恰好包含 k 对手套的方案数,对 10^9+7 取模。

多测,T \le 10^5,n \le 10^3, 1 \le m \le 2n, 1\le k \le n,1 秒,512 MB。

:::::success[题解] 分两步:

:::::info[代码]

const int N = 2005;
comb<mint, N> C(N-1);
int n, m, k;

void _main() {
    cin >> n >> m >> k;
    cout << C(n, k) * mint(2).pow(m - 2 * k) * C(n - k, m - 2 * k) << '\n';
}

:::::

:::::success[另解] 二元 GF 刻画之,用 x 的幂表示取出的手套总数,y 的幂表示配对成功的手套对数。

一对手套的 GF 为 1+2x+x^2y。则答案为 [x^m y^k] \left(1+2x+x^2y\right)^n。于是

\begin{aligned} \left(1+2x+x^2y\right)^n&=\sum_{i=0}^n \binom{n}{i} (1+2x)^{n-i} (x^2y)^i\\ [y^k] \left(1+2x+x^2y\right)^n &=\binom{n}{k} (1+2x)^{n-k} x^{2k}\\ [y^k] \left(1+2x+x^2y\right)^n &=\binom{n}{k} x^{2k} \sum_{j=0}^{n-k} \binom{n-k}{j} 2^j x^j\\ [x^{m-2k}] (1+2x)^{n-k}&=\binom{n-k}{m-2k} 2^{m-2k}\\ [x^m y^k] \left(1+2x+x^2y\right)^n &= \binom{n}{k} \binom{n-k}{m-2k} 2^{m-2k} \end{aligned}

:::::

P6075 [JSOI2015] 子集选取

给出 n,k,你需要选择若干个 A_{i,j} \subseteq \{1,2,\cdots,n\},其中 1 \le j \le i \le k,排成一个三角矩阵后,满足 A_{i,j} \subseteq A_{i,j-1} \land A_{i,j} \subseteq A_{i-1,j}。求方案数,对 10^9+7 取模。

:::::success[题解] 从特殊到一般,讨论 n=1。容易证明此时存在一条上升路径将整个三角形分成全 \varnothing 和全 \{1\} 的两部分。因为每一步有向上和向右两种选择,走 k 步答案为 2^k。

类似地,对于一个一般的 n,根据题目中所给性质可以发现一共有 n 条路径。因此答案为 (2^k)^n=2^{kn}。复杂度 O(\log n)。

:::::info[代码]

#define int long long
int n, k;
void _main() {
    cin >> n >> k;
    cout << mint(2).pow(n * k);
} 

:::::

【无题解】P1350 车的放置

【无题解】CF1436C Binary Search

【无题解】P9306 「DTOI-5」进行一个排的重 (Minimum Version)

【无题解】ARC214C Divide into 4 Teams

【无题解】P8865 [NOIP2022] 种花

【无题解】CF1207D Number Of Permutations

【无题解】P1450 [HAOI2008] 硬币购物

【无题解】P6475 [NOI Online #2 入门组] 建设城市

【无题解】P5377 [THUPC 2019] 鸽鸽的分割

【无题解】CF785D Anton and School - 2

【无题解】P10185 [YDOI R1] Necklace

【无题解】CF1738E Balance Addicts

【无题解】CF1227F2 Wrong Answer on test 233 (Hard Version)

【无题解】P5689 [CSP-S2019 江西] 多叉堆

【无题解】CF1332E Height All the Same

【无题解】CF1696E Placing Jinas

P3330 [ZJOI2011] 看电影

有 n 人前来看电影,共有 k 个座位。每人依次入场,从 1 \sim k 中随机选择一个正整数 p。若 p 无人则坐在 p,否则令 p \gets p+1 并继续上述操作。若 p>n 则无法落座。

求所有人都有座位的概率。需要高精度。

多测,T \le 50,n,k \le 200,1 秒,125 MB。

:::::success[题解] 特判 k<n 的情况。

概率转计数,总方案显然有 k^n 种,考虑计算合法方案数。

在 k 后方新增一个陷阱座位,然后将 k+1 个座位拉成环,这样所有人一定有座位,根据圆排列的知识可以得到方案数为 (k+1)^{n-1}。

此时合法当且仅当陷阱上没有人。由于环是旋转对称的,直接从 k+1-n 个空座位中选出一个陷阱即可。于是得到答案式子

\dfrac{(k+1)^{n-1} (k+1-n)}{k^n}

:::::

:::::info[代码]

from math import gcd
T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    if k < n:
        print('0 1')
        continue
    a = ((k + 1) ** (n - 1)) * (k + 1 - n)
    b = k ** n
    print(a // gcd(a, b), b // gcd(a, b))

:::::

【无题解】ARC203C Destruction of Walls

【未完成】ABC240G Teleporting Takahashi

你位于一个无限大的三维空间中,初始坐标 (0,0,0)。一步可以将三维坐标之一加 1 或减 1。求恰好 n 步后位于 (x,y,z)

【无题解】P14636 [NOIP2025] 清仓甩卖

【无题解】AT_code_festival_2017_quala_e Modern Painting