提交记录

代码

C++代码，非C++选手请不要看

#include <bits/stdc++.h>
using namespace std;
string add(string a, string b) {
    string res;
    int carry = 0, sum;
    if (a.size() < b.size()) swap(a, b);
    b.insert(0, a.size() - b.size(), '0');
    for (int i = a.size() - 1; i >= 0; i--) {
        sum = (a[i] - '0') + (b[i] - '0') + carry;
        carry = sum / 10;
        res += (sum % 10) + '0';
    }
    if (carry) res += '1';
    reverse(res.begin(), res.end());
    return res;
}
string multiply(string a, string b) {
    int len1 = a.size(), len2 = b.size();
    vector<int> res(len1 + len2, 0);
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = res[i + j + 1] + mul;
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    string result;
    for (int num : res) {
        if (!(result.empty() && num == 0))
            result += (num + '0');
    }
    return result.empty() ? "0" : result;
}
string stirling[51][51];
int main() {
    int n, m;
    cin >> n >> m;
    if (m == 0 || m == 1) {
        cout << m;
    } else if (m == n) {
        cout << 1;
    } else if (m > n) {
        cout << 0;
    } else {
        for (int i = 2; i <= m; i++) {
            stirling[i][i] = "1";
        }
        for (int i = m; i <= n; i++) {
            stirling[i][m] = add(multiply(to_string(m), stirling[i-1][m]), stirling[i-1][m-1]);
        }
        cout << stirling[n][m];
    }
    return 0;
}

代码思路

以下内容含有数学知识，如果没有学过数学的可以不用看

把 $n$ 只小猪放到 $m$ 个房间里，方法数为 $S(n,m)$，其中 $S$ 代表 Stirling，即斯特林数

不难看出，由于房间都是砖头做的，没有区别，因此要用第二类斯特林数（斯特林子集数）。

第二类斯特林数的规律为：
若 $n=m$ 则 $S(n,m)=1$
若 $n<m$ 则 $S(n,m)=0$
否则 $S(n,m)=m×S(n-1,m)+S(n-1,m-1)$

由于第二类 Stirling 数增长很快，根据题目数据范围 $1<=n<=50$ 且 $0<=n<=50$，可预测结果会爆 long long，因此要用高精度。 此处使用 string 类型处理，添加高精度加法 add 和乘法 multiply 函数。

代码框架

if (m == 0 || m == 1) { // 如果 m 等于 0 或者 1，则 S(n,m) = m
    cout << m;
} else if (m == n) { // m = n 时，S(n,m) = 1
    cout << 1;
} else if (m > n) { // m > n 时，S(n,m) = 0
    cout << 0;
} else { // 其它情况，用斯特林数递推公式 S(n,m) = m × S(n-1,m) + S(n-1,m-1)
    for (int i = 2; i <= m; i++) { // 存储 m = n 时的 Stirling 数
        stirling[i][i] = "1";
    }
    for (int i = m; i <= n; i++) { // 利用递推公式
        stirling[i][m] = add(multiply(to_string(m), stirling[i-1][m]), stirling[i-1][m-1]);
    }
    cout << stirling[n][m]; // 输出结果
}

帮助的必关， $20$ 分求调。