比赛 20250904开学热身赛 评测结果 AAAAAAAAAA
题目名称 苹果树 最终得分 100
用户昵称 健康铀 运行时间 0.743 s
代码语言 C++ 内存使用 10.62 MiB
提交时间 2025-09-04 21:31:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	freopen("2018tree.in","r",stdin);
	freopen("2018tree.out","w",stdout);
    int n, P;
    cin >> n >> P;
    
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<ll> fac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % P;
    }
    
    vector<vector<ll>> C(n + 1, vector<ll>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
        }
    }
    
    ll ans = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            ll term = j * (n - j) % P;
            term = term * C[n - i][j - 1] % P;
            term = term * fac[j] % P;
            term = term * i % P * (i - 1) % P;
            term = term * fac[n - j - 1] % P;
            ans = (ans + term) % P;
        }
    }
    
    cout << ans % P << endl;
    
    return 0;
}