c/c++语言开发共享洛谷P4492 [HAOI2018]苹果树(组合数)

题意

题目链接

sol

有点自闭，。我好像对组合数一窍不通(~~~~)

orz shadowice

// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll long long  int mod; template<typename a, typename b> inline bool chmax(a &x, b y) {return x < y ? x = y, 1 : 0;} template<typename a, typename b> inline bool chmin(a &x, b y) {return x > y ? x = y, 1 : 0;} template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;} template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);} template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;} template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;} #define ll long long  using namespace std; const int maxn = 2001, inf = 1e9 + 10; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } ll n, fac[maxn], c[maxn][maxn]; signed main() {     n = read(); mod = read();     fac[0] = 1;     for(int i = 1; i <= n; i++) fac[i] = mul(i, fac[i - 1]);     for(int i = 0; i <= n; i++) {         c[i][0] = c[i][i] = 1;         for(int j = 1; j < i; j++) c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);     }     ll res = 0;     for(int i = 2; i <= n; i++) {         ll ans = 0;         for(int j = 1; j <= n - i + 1; j++) {             add2(ans, 1ll * fac[j] % mod * c[n - i][j - 1] % mod * j % mod * (n - j) % mod * fac[n - j - 1] % mod * i % mod * (i - 1) % mod);         }         add2(res, ans);     }     cout << res;     return 0; } /* 6 2 5 2 3 5 4 1 1 1 2 4 */