【数学】排列组合

· · 个人记录

排列组合是数学中非常重要的知识，它其实是排列与组合的统称。

排列

咕咕咕。

组合

组合指从 n 个东西中选出 k 个，不用排序。

例如，洛谷里面有 100 个管理员，想要选出 50 个给予双重 \texttt{tag}，问有多少种方法。

这道题中，只要选出来了就给两个 \texttt{tag}，不考虑先后，就可以用组合来解决。

数学中规定：从 n 个东西中选出 k 个，表示为 C^k_n，公式为：

C^k_n = \dfrac{n!}{k! \times (n-k)!}

例如：

C^2_4 = \dfrac{4!}{2! \times (4-2)!} = \dfrac{24}{4} = 6

再返回洛谷管理员那道题，答案显而易见，C^{50}_{100} = \dfrac{100!}{50! \times (100-50)!} = \cdots\cdots

例题

1. 洛谷P8557

这是一道简单的排列组合问题。

我们可以先从这 n 种金属入手，对于任意一种金属，它可以被任意 1 \sim k 个熔炉所造出来，方案总数为：

C^1_k+C^2_k+C^3_k+\cdots\cdots+C^{k-1}_k+C^k_k = 2^k-1

现在有 n 种金属，每一种金属有 2^k-1 种方法，总方案数为 (2^k-1)^n，配上快速幂模板即可。

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
using namespace std;
const int mod = 998244353;

int ksm(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k, ans = 0;
    cin >> n >> k;
    cout << ksm(ksm(2, k)-1, n) << endl;
    return 0;
}