「做题记录」组合计数选做
stripe_python · · 算法·理论
写的是主要难点在组合数学上的题。计数 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[题解]
注意到对于一个形如
| 复杂度 |
|---|
:::::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[题解] 分两步:
- 钦定
k 对手套,方案数\binom{n}{k} ; -
在剩余 n-k 对手套中找出m-2k 只不同组的手套,注意左右手套不同,方案数\binom{n-k}{m-2k} \times 2^{m-2k} 。
:::::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 刻画之,用
一对手套的 GF 为
:::::
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[题解]
从特殊到一般,讨论
| 类似地,对于一个一般的 |
|---|
:::::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[题解]
特判
概率转计数,总方案显然有
在
此时合法当且仅当陷阱上没有人。由于环是旋转对称的,直接从
:::::
:::::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)