Ta có công thức để tính giá trị kỳ vọng là ~S / \binom{M + 1}{2}~, với:

• ~S~ là tổng độ đa dạng của mọi cặp (~L, R~) có thể chọn.

• ~\binom{M + 1}{2}~ là số lượng cặp (~L, R~) thỏa mãn ~1 \le L \le R \le M~, dễ thấy đây là một hằng số.

Vì các cặp số (~L, R~) có xác suất được chọn bằng nhau nên ta thu được công thức trên. Ngoài ra, mẫu số là hằng số nên ~S~ tỉ lệ thuận với giá trị kỳ vọng, bài toán tương đương đếm số cách chia quà vào các túi sao cho ~S~ đạt giá trị lớn nhất có thể.

Đến đây, ta sẽ đi tính contribution của từng loại quà vào tổng ~S~, nói ngắn gọn là với loại quà thứ ~i~, ta cần tính xem có bao nhiêu cặp (~L, R~) mà đảm bảo ông già Noel lấy được ít nhất một hộp quà loại thứ ~i~. Vậy ta có 2 trường hợp sau:

Trường hợp 1: ~a_i \le M~.

Với mỗi túi chứa ít nhất một hộp quà loại ~i~, ta đánh số cho chúng lần lượt từ trái sang phải là ~0, 1, \dots, a_i + 1~, trong đó túi số ~0~ ở vị trí ~0~ và túi số ~a_i + 1~ ở vị trí ~M + 1~ tính từ trái sang (hiển nhiên 2 túi quà này không hề tồn tại mà chỉ là quy ước). Gọi ~diff_k~ là khoảng cách từ túi thứ ~k~ đến túi quà gần nhất về bên phải của nó mà chứa hộp quà loại ~i~.

Để tính contribution của các hộp quà thuộc loại ~i~, ta có công thức: ~\binom{M + 1}{2} - \sum_{k = 0}^{a_i}\binom{diff_k}{2}~.

• ~\binom{M + 1}{2}~ là số lượng cặp (~L, R~) thỏa mãn ~1 \le L \le R \le M~.

• ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ là số lượng cặp (~L, R~) mà không túi nào từ ~L~ đến ~R~ có hộp quà thuộc loại ~i~.

Vậy theo nguyên tắc loại trừ ta thu được công thức trên, mặt khác vì ~\binom{M + 1}{2}~ là một hằng số nên để contribution là tối đa thì ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ phải đạt giá trị tối thiểu. Ngoài ra, cần thỏa mãn một điều kiện hiển nhiên là ~\sum_{k = 0}^{a_i} diff_k = M + 1~.

Nhận xét: ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ đạt giá trị tối thiểu khi và chỉ khi chênh lệch tối đa giữa 2 phần tử thuộc dãy ~diff_0, \dots, diff_{a_i}~ là không quá ~1~.

Chứng minh: Nếu ~diff_1 - diff_0 > 1~ thì ~\binom{diff_1}{2} + \binom{diff_0}{2} > \binom{diff_1 - 1}{2} + \binom{diff_0 + 1}{2}~ dẫn đến tổng ~\sum_{k = 0}^{a_i}\binom{diff_k}{2}~ không đạt giá trị tối thiểu (tương tự với các cặp phần tử khác).

Vậy ta cần đếm số dãy ~diff_0, \dots, diff_{a_i}~ thỏa mãn:

• Chênh lệch tối đa giữa 2 phần tử không quá ~1~.

• ~\sum_{k = 0}^{a_i} diff_k = M + 1~.

Nhận xét: Gọi ~x~ là số phần tử có giá trị khác ~min(diff_0, \dots, diff_{a_i})~, dễ thấy ~x < a_i + 1~. Mặt khác, vì chênh lệch giữa 2 phần tử bất kỳ không vượt quá ~1~ đơn vị nên ~min(diff_0, \dots, diff_{a_i}) = (M + 1 - x) / (a_i + 1)~. Vì vậy, chỉ có duy nhất 1 giá trị phù hợp là ~x = (M + 1) \mod (a_i + 1)~.

Kết luận: Đặt ~z = (M + 1 - x) / (a_i + 1)~ thì:

• ~S_{max} = \binom{M + 1}{2} - (a_i + 1 - x) \cdot \binom{z}{2} - x \cdot \binom{z + 1}{2}~.

• Số cách chia dãy thỏa mãn là ~\binom{a_i + 1}{x}~.

Trường hợp 2: ~a_i \gt M~.

Đây là 1 corner case có thể khiến thí sinh mất điểm nhưng một khi nhận ra thì rất dễ giải quyết. Vì ~a_i > M~ nên ta cứ chia sẵn 1 hộp quà vào mỗi túi, lúc này ~(a_i - M)~ hộp quà còn lại được phép chia tùy ý vì chúng không ảnh hưởng đến tổng ~S~. Để tính số cách, ta chỉ việc áp dụng trực tiếp công thức chia kẹo Euler.

Kết luận:

• ~S_{max} = \binom{M + 1}{2}~.

• Số cách chia dãy thỏa mãn là ~\binom{a_i - 1}{M - 1}~.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, MAX = 1e6 + 5, MOD = 998'244'353;
int T, n, m;
int a[N];
int gt[MAX], inv[MAX];
int Pow(int A, int B) {
    int ans = 1;
    while (B) {
        if (B & 1) ans = 1ll * ans * A % MOD;
        A = 1ll * A * A % MOD, B >>= 1;
    }
    return ans;
}
void prepare() {
    gt[0] = 1;
    for (int i = 1; i < MAX; i++) gt[i] = 1ll * gt[i - 1] * i % MOD;
    inv[MAX - 1] = Pow(gt[MAX - 1], MOD - 2);
    for (int i = MAX - 1; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % MOD;
}
int C(int k, int n) {
    if (k < 0 || k > n) return 0;
    return 1ll * gt[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int C2(int n) {
    if (n < 2) return 0;
    return (1ll * n * (n - 1) / 2) % MOD;
}
void add(int &A, int B) {
    A += B;
    if (A >= MOD) A -= MOD;
}
void sub(int &A, int B) {
    add(A, MOD - B);
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }
    cin >> T;
    cin >> n >> m;
    for (int i = 1; i <=n; i++) cin >> a[i];
    if (T == 1) {
        int sum = 0, choose = C2(m + 1);
        for (int i = 1; i <= n; i++) {
            add(sum, choose);
            if (a[i] <= m) {
                int x = (m + 1) % (a[i] + 1);
                int z = (m + 1) / (a[i] + 1);
                sub(sum, 1ll * (a[i] + 1 - x) * C2(z) % MOD);
                sub(sum, 1ll * x * C2(z + 1) % MOD);
            }
        }
        cout << 1ll * sum * Pow(choose, MOD - 2) % MOD << '\n';
    }
    else {
        prepare();
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= m) {
                int x = (m + 1) % (a[i] + 1);
                sum = 1ll * sum * C(x, a[i] + 1) % MOD;
            }
            else sum = 1ll * sum * C(m - 1, a[i] - 1) % MOD;
        }
        cout << sum << '\n';
    }
    return 0;
}