什么是排列组合

排列组合是计数问题，顺序不同且值相同算两种方案是排列，顺序不同且值相同算一种方案是组合。

暴力枚举方案能算出方案数，太耗时，运用加法原理和乘法原理可降低时间复杂度。先将原问题拆解成子问题，根据子问题间的关系确定用加法原理还是乘法原理来合并问题的解，求出原问题的解。

计数问题的关键是不重复不遗漏，加法原理和乘法原理是计数问题的重要思想。

很多算法都有拆解（划分）子问题的思想，拆解子问题可简化原问题，方便求解。

暴力枚举是算法的基础，算法是为了优化时间或空间，或着解决用枚举求解起来复杂的问题。

加法原理

本质是求和。子问题间独立，每个子问题计数的都是有几个方案，都已达成目标，那么累加子问题的解。这就是加法原理。

乘法原理

本质是总数 = 每份数×份数。

子问题间不独立，每个子问题都是完整方案的一步，未达到目标。

设当前子问题有x个方法，这x个方法可配之前子问题的方法，如下图，x是份数，之前子问题的方法数是每份数，相乘得解。

排列数

P(n, m) 是排列数，表示n个中选m个的方案数，P(n, m) = n × (n - 1) × (n - 2) ×....× (n - m + 1)，如下图。

组合数

C(n, m)表示n个中取m个的组合数，明确排列数和组合数的区别，组合数可由排列数求出，需去重。排列数里方案是相同值不同顺序的算多个，但在组合数里算一个。

用除法去重，总数：P(n, m)，每份数：值同顺序不同的排列即P(m, m)，求份数。

关键是理解排列数公式、组合数公式的本质，排列数公式、组合数的公式由排列组合的性质得出。

组合数与杨辉三角

组合数和杨辉三角对应，杨辉三角的规律可应用于组合数。

如何对应

如下图，行起始和列起始为0时，vct[i][j] = C(i, j)。

杨辉三角规律得出组合数定理

1. vct[i][j] = vct[i - 1][j - 1] + vct[i - 1][j]，即C(i, j) = C(i - 1, j - 1) + C(i - 1, j)。

通过递推理解，到第j个有两个决策，选或不选，选：i - 1的部分选j - 1个，不选：i - 1的部分选j个，如下图。

2. 2^i = vct[i][0] + vct[i][1] + vct[i][2] +...+ vct[i][i] = C(i, 0) + C(i, 1) + C(i, 2) +...+ C(i, i)

结合组合数的意义和二进制数理解，C(i, j)（0 <= j <= i)想从i为二进制里取j个1有几种取法，用二进制数表示[0, 2^i - 1]，共2^i个数，所以等于2^i。

3.vct[i][i] + vct[i + 1][i] + vct[i + 2][i] +...+ vct[i + k][i] = vct[i + k + 1][i + 1]，即C(i, i) + C(i + 1, i) + C(i + 2, i) +...+ C(i + k, i) = C(i + k + 1, i + 1)

公式的图如下：

杨辉三角递推理解如下图：

还可用组合数递推理解。

4.还有一个，待会儿再写

题目

洛谷 B4031 [语言月赛 202409] 始终

B4031 [语言月赛 202409] 始终 - 洛谷

暴力枚举所有“好的”字符串同时计数，若子串不连续，暴力枚举会超时。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;typedef long long LL;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string str;cin >> str;LL res = 0;for (LL i = 0; i < str.size(); ++i) {for (LL j = i; j < str.size(); ++j) {if (str[i] == str[j])  ++res;}}cout << res;return 0;
}

洛谷 P1358 扑克牌

P1358 扑克牌 - 洛谷

每个人拿完牌后当前方案还未完成，是乘法原理。

当前方案每张牌只能出现一次，第i人不能拿第[1, i -1]人拿的num张牌，第i人是在n - num中选ai张牌，值同顺序不同算一种方案，是组合数。

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Mo = 10007;LL f_pow(LL a, LL p) {LL ans = 1, b = (a % Mo);while (p > 0) {if ((p & 1) != 0)  ans = (ans * b) % Mo;b = (b * b) % Mo;p >>= 1;}return ans;
}LL C(LL n, LL m) {LL num1 = 1, num2 = 1;for (LL i = 1; i <= m; ++i) {num1 = (num1 * (n - i + 1)) % Mo;num2 = (num2 * i) % Mo;}return (num1 * f_pow(num2, Mo - 2)) % Mo;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, a;cin >> n >> m;LL num = n, res = 1;for (LL i = 1; i <= m; ++i) {cin >> a;res = (res * C(num, a)) % Mo;num -= a;}cout << res;return 0;
}

洛谷 B4185 倍数子串/子串

B4185 [中山市赛 2024/科大国创杯小学组 2023] 倍数子串/子串 - 洛谷

一个整数，末两位能被4整除，是4的倍数，最后一位是0或5，是5的倍数。

若一个长度≤2的子串，是4的倍数或5的倍数，可和之前任意连续子串组合成4或5的倍数，用乘法原理，x × 1 = x，所以最后直接加没有乘。

既是4的倍数又是5的倍数，4的倍数的情况不计算，5的倍数的情况计算，避免重复，得出的答案正确，若改成4的倍数的情况计算，5的倍数的情况不计算，会漏算[i, i]子串（此时str[i]不是4的倍数不会被记录）。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;typedef long long LL;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string str;cin >> str;LL res = 0;for (LL i = 0; i < str.size(); ++i) {if (str[i] == '0' || str[i] == '5')  res += i + 1;else {if ((static_cast<LL> (str[i] - '0')) % 4 == 0)  ++res;if (i > 0 && (static_cast<LL> (str[i - 1] - '0') * 10 + static_cast<LL> (str[i] - '0')) % 4 == 0)  res += i;}}cout << res;return 0;
}

2024年12月月赛 丙组 T5 查找404

上海市计算机学会竞赛平台 | YACS

先考虑无“*”：

• 方案总数：任意4可和前面的所有40组成404，乘法原理，只有一个4，是×1，res加num40。
• 40个数：4和0不连续，任意0可和前面的4组成40，若当前为0，num40加num4即可。

考虑“*”：

当前是“*”， res、num40、num4需×2。

“*”有两种状态，每个当前已产生的字符串可分出两个字符串，所以需翻倍，每次num4 += p（p记录翻了几倍，当前所有字符串都包含4，所以+=p）。
此时num4、num40为所有字符串的40和4的个数，res为结果。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;typedef long long LL;const LL Mo = 1e9 + 7;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL t, n;string str;cin >> t;LL res = 0, num4 = 0, num40 = 0, p = 1;while (t--) {cin >> n >> str;res = 0, num4 = 0, num40 = 0, p = 1;for (LL i = 0; i < n; ++i) {if (str[i] == '4') {num4 = (num4 + p) % Mo;res = (res + num40) % Mo;} else if (str[i] == '0') {num40 = (num40 + num4) % Mo;} else if (str[i] == '*') {res = (res * 2 + num40) % Mo;num40 = (num40 * 2 + num4);num4 = (num4 * 2 + p) % Mo;p = (p * 2) % Mo;}}cout << res << '\n';}return 0;
}

洛谷 P2392 kkksc03考前临时抱佛脚

P2392 kkksc03考前临时抱佛脚 - 洛谷

若左脑（或右脑）已做完，右脑（或左脑）未做完，左脑可继续做题。

开始想过状压dp，dp[i][j] = 第i科做题状态为j（二进制，题已做对应位为1），如上条件存在，导致不能单纯枚举最后做的两道题，换思路。

贪心，局部最优：左脑和右脑算题时间差距最小，全局最优：最大值最小，多次计算可合并为一次计算。求加上若干做题时间后，<=sum（sum为当前科做题的总时间） / 2的最大值，sum减去该值得到结果。

用dp解：

• 状态：dp[i][j] = 第i科里 ≤j时间的最大时间
• 状态转移方程：dp[i][j] = max(dp[i][j], dp[i][j - vct[i]] + vct[i])（vct[i]是当前题的时间，vct[i] ≤ j）
• 边界：dp[i][j] = 0
• 结果： dp[i][bagw]

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL n = 4;
const LL Maxs = 20 + 5;
const LL Maxbw = 20 * 60 / 2 + 5;LL nums[n + 2], dp[Maxbw], vct[Maxs];void init(LL mVal) {for (LL i = 0; i <= mVal; ++i)  dp[i] = 0;return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> nums[0] >> nums[1] >> nums[2] >> nums[3];LL sum = 0, bagw = 0, res = 0;for (LL i = 0; i < n; ++i) {sum = 0;for (LL j = 0; j < nums[i]; ++j) {cin >> vct[j];sum += vct[j];}bagw = sum / 2;init(bagw);for (LL j = 0; j < nums[i]; ++j) {for (LL k = bagw; k >= vct[j]; --k)dp[k] = max(dp[k], dp[k - vct[j]] + vct[j]);}res += sum - dp[bagw];}cout << res;return 0;
}

总结

较为复杂的排列组合问题，分步求解，每一步将原问题拆解成子问题，根据子问题间的关系选择用加法原理还是乘法原理。

排列组合的关键是拆解子问题。