TIOJ 2265：殿壬的飲料王國

TIOJ 2265：殿壬的飲料王國

題目大意：有 $n\times m$ 個人，有 $m$ 個人有 $1$ 塊零錢，有 $m$ 個人有 $2$ 塊零錢，$\dots$，有 $m$ 個人有 $n$ 塊零錢。這些人要去買飲料，一個飲料要 $1$ 塊錢，總共會分兩組，第一組買完飲料第二組才能買，有 $i$ 塊零錢的人有 $a_i$ 人在第一組，有 $b_i$ 人在第二組，$a_i + b_i = m$。店家一開始沒有任何零錢，只能由之前客人付的錢去找，問你有幾種買飲料的順序可以使店家對每個人都有零錢找。

解法：付 $2$ 塊錢的人都要用 $1$ 塊錢找，於是 $1$ 塊錢找光，付 $3$ 塊錢的只能用 $2$ 塊錢找，依此類推 $k$ 塊錢只能由 $k-1$ 塊找，於是在每個時刻 $k-1$ 塊錢的數量都要大於等於 $k$ 塊錢的數量，這可以變成給你一個每行長度為 $a_1,a_2,\dots,a_n$ 的表，你要依序填入數字使得每行數字遞增，每列數字遞增，根據勾長公式，令一個格子的 $\text{hook}$ 為他右邊與上面格子的數量 $+1$，那方法數有 $\frac{(\sum\limits_{i = 1}^na_i)!}{\prod\limits_v\text{hook}_v}$ 種。所以我們先判斷 $a$ 是不是遞減的，算出第一組的答案後，我們將 $a_i$ 變成 $m - a_i$，算第二組的答案，最後乘以 $\prod\limits_{i = 1}^na_i!\times(m - a_i)!$ 就可以了。

$\text{Code：}$

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int N = 1e6 + 5;

int n, m, tot, ans;
int a[N], c[N];
int pro[N], inv[N];

void deal() {
    for (int i = 1; i <= n; i++) {
        ans = 1ll * ans * pro[a[i]] % MOD;
        for (int j = 1; j <= a[i]; j++) c[j]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= a[i]; j++) {
            ans = 1ll * ans * inv[c[j] + a[i] - j] % MOD;
            c[j]--;
        }
    }
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    cin >> n >> m;
    a[0] = N;
    for (int i = 1; i <= n; i++) {
        int foo;
        cin >> a[i] >> foo;
        if (a[i] > a[i - 1]) {
            cout << "0\n";
            return 0;
        }
        tot += a[i];
    }
    tot = max (tot, n * m - tot);
    pro[0] = pro[1] = inv[1] = 1;
    for (int i = 2; i <= tot; i++) {
        pro[i] = 1ll * pro[i - 1] * i % MOD;
        inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    ans = 1ll * pro[tot] * pro[n * m - tot] % MOD;
    deal();
    for (int i = 1; i <= n; i++) a[i] = m - a[i];
    reverse (a + 1, a + n + 1);
    deal();
    cout << ans << '\n';
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！