【2021牛客寒假第五場】B-比武招親（上）排列組合

題意

思路

考 慮 最 大 值 和 最 小 值 貢 獻 ， 考慮最大值和最小值貢獻， 考慮最大值和最小值貢獻，

先 看 最 大 值 ： 先看最大值： 先看最大值：
假 設 我 們 選 擇 最 大 值 為 x ， 則 剩 下 m ? 1 個 位 置 只 能 選 不 超 過 x 的 數 字 假設我們選擇最大值為x，則剩下m-1個位置只能選不超過x的數字 假設我們選擇最大值為x，則剩下m?1個位置只能選不超過x的數字
題 目 表 示 排 完 序 之 后 本 質 不 同 ! \red{題目表示排完序之后本質不同!} 題目表示排完序之后本質不同!
所 以 就 是 在 不 超 過 x 的 數 字 中 任 意 重 復 選 擇 m ? 1 個 并 且 生 成 不 遞 減 序 列 的 個 數 ， 所以就是在不超過x的數字中任意重復選擇m-1個并且生成不遞減序列的個數， 所以就是在不超過x的數字中任意重復選擇m?1個并且生成不遞減序列的個數，

沒 錯 ， n 個 中 選 m 個 數 ( 可 重 復 ) 且 不 遞 減 序 列 個 數 為 C n + m ? 1 m ， 請 自 行 百 度 ！ 沒錯，n個中選m個數(可重復)且不遞減序列個數為C_{n+m-1}^{m}，請自行百度！ 沒錯，n個中選m個數(可重復)且不遞減序列個數為Cn+m?1m?，請自行百度！

x = n 時 ， 貢 獻 為 n ? C n + m ? 2 m ? 1 x=n時，貢獻為n*C_{n+m-2}^{m-1} x=n時，貢獻為n?Cn+m?2m?1?
x = n ? 1 時 ， 貢 獻 為 ( n ? 1 ) ? C n ? 1 + m ? 2 m ? 1 x=n-1時，貢獻為(n-1)*C_{n-1+m-2}^{m-1} x=n?1時，貢獻為(n?1)?Cn?1+m?2m?1?
…

所 以 我 們 最 大 值 的 貢 獻 就 是 所以我們最大值的貢獻就是 所以我們最大值的貢獻就是

∑ i = 1 n ( n ? i + 1 ) ? C n ? i + 1 + m ? 2 m ? 1 \sum_{i=1}^n(n-i+1)*C_{n-i+1+m-2}^{m-1} i=1∑n?(n?i+1)?Cn?i+1+m?2m?1?

同 理 ， 最 小 值 就 是 m ? 1 個 位 置 必 須 選 擇 不 小 于 x 的 數 字 ， 貢 獻 就 是 同理，最小值就是m-1個位置必須選擇不小于x的數字，貢獻就是 同理，最小值就是m?1個位置必須選擇不小于x的數字，貢獻就是

∑ i = 1 n i ? C n ? i + 1 + m ? 2 m ? 1 \sum_{i=1}^ni*C_{n-i+1+m-2}^{m-1} i=1∑n?i?Cn?i+1+m?2m?1?

這 兩 個 式 子 是 我 化 簡 過 后 的 ， 難 點 就 是 不 遞 減 序 列 個 數 是 多 少 ， \red{這兩個式子是我化簡過后的，難點就是不遞減序列個數是多少，} 這兩個式子是我化簡過后的，難點就是不遞減序列個數是多少，

兩 個 減 一 減 得 ： 兩個減一減得： 兩個減一減得：

∑ i = 1 n ( n ? i + 1 ) ? C n ? i + m ? 1 m ? 1 \sum_{i=1}^n(n-i+1)*C_{n-i+m-1}^{m-1} i=1∑n?(n?i+1)?Cn?i+m?1m?1?

Code(44MS)

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll f[N], invF[N], inv[N];
void Init()
{
    f[0] = f[1] = inv[0] = inv[1] = invF[0] = invF[1] = 1;
    for(int i = 2;i < N; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inv[i] = mod - (mod / i) * inv[mod % i] % mod;
        invF[i] = invF[i - 1] * inv[i] % mod;
    }
}

ll C(ll m, ll n)
{
    if(m < 0 || n < 0 || n > m)
        return 0;
    ll ans = f[m];
    ans = ans * invF[n] % mod;
    ans = ans * invF[m - n] % mod;
    return ans;
}

//ll quick_pow(ll a, ll b) {
//    ll ans = 1;
//    while(b) {
//        if(b & 1) ans = ans * a % mod;
//        a = a * a % mod;
//        b >>= 1;
//    }
//    return ans % mod;
//}

void solve() {
    Init();
    ll n, m; cin >> n >> m;
    ll ans = 0;
    // C(n + m - 1, m) n個數中選m個不遞減個數
    for(ll i = 1;i <= n; i++) {
        // cout << "個數：" << C(n - i + 1 + m - 1 - 1, m - 1) << endl;
        ans = (ans + (n - 2 * i + 1) * C(n - i + m - 1, m - 1) % mod) % mod;
    }
    cout << (ans % mod + mod) % mod << endl;
}

signed main() {
    solve();
}