1#include <iostream>
2using namespace std;
3
4// 计算阶乘
5long long factorial(int n) {
6    long long res = 1;
7    for (int i = 2; i <= n; i++) {
8        res *= i;
9    }
10    return res;
11}
12
13// 计算多重集合排列数
14// cnt[i] 表示第 i 种元素的个数
15long long multisetPermutation(int cnt[], int k) {
16    int total = 0;
17    for (int i = 0; i < k; i++) {
18        total += cnt[i];
19    }
20    long long res = factorial(total);
21    for (int i = 0; i < k; i++) {
22        res /= factorial(cnt[i]);
23    }
24    return res;
25}
26
27int main() {
28    // MISSISSIPPI: M=1, I=4, S=4, P=2
29    int cnt[] = {1, 4, 4, 2};
30    cout << "MISSISSIPPI 的排列数: "
31         << multisetPermutation(cnt, 4) << endl;
32    return 0;
33}

1#include <iostream>
2using namespace std;
3
4// 计算组合数 C(n, r)
5long long C(int n, int r) {
6    if (r > n - r) r = n - r; // 优化
7    long long res = 1;
8    for (int i = 0; i < r; i++) {
9        res = res * (n - i) / (i + 1);
10    }
11    return res;
12}
13
14int main() {
15    int k, r;
16    cout << "输入元素种类数 k 和选取个数 r: ";
17    cin >> k >> r;
18    // 从 k 种元素中可重复选 r 个的方案数
19    cout << "组合数: " << C(r + k - 1, r) << endl;
20    return 0;
21}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5long long C(int n, int r) {
6    if (r < 0 || n < r) return 0;
7    if (r > n - r) r = n - r;
8    long long res = 1;
9    for (int i = 0; i < r; i++) {
10        res = res * (n - i) / (i + 1);
11    }
12    return res;
13}
14
15// upper[i] 为第 i 种元素的上界
16long long multisetCombination(vector<int>& upper, int r) {
17    int k = upper.size();
18    long long ans = 0;
19    // 枚举所有子集进行容斥
20    for (int mask = 0; mask < (1 << k); mask++) {
21        int bits = __builtin_popcount(mask);
22        int subtract = 0;
23        for (int i = 0; i < k; i++) {
24            if (mask & (1 << i)) {
25                subtract += upper[i] + 1;
26            }
27        }
28        long long val = C(r - subtract + k - 1, k - 1);
29        if (bits % 2 == 0) ans += val;
30        else ans -= val;
31    }
32    return ans;
33}
34
35int main() {
36    // 示例：从 {3·a, 2·b, 1·c} 中选 4 个
37    vector<int> upper = {3, 2, 1};
38    int r = 4;
39    cout << "组合数: " << multisetCombination(upper, r) << endl;
40    // 输出: 6
41    return 0;
42}