Phân tích Giải thuật

1. Biến đổi Kỳ vọng qua Số Stirling loại hai

Theo công thức đổi cơ sở lũy thừa sang giai thừa giảm (Falling Factorial), ta có:

trong đó \(\left\{ \begin{matrix} K \\ j \end{matrix} \right\}\) là số Stirling loại hai, và \(x^{\underline{j}} = x(x-1)\dots(x-j+1)\).

Do tính chất tuyến tính của kỳ vọng:

2. Mối liên hệ bất ngờ với Đạo hàm của Hàm sinh (Probability Generating Function)

Hàm sinh xác suất (PGF) của biến ngẫu nhiên \(X = \sum_{i=1}^N X_i\) là:

Lấy đạo hàm cấp \(j\) của \(P(z)\) theo \(z\):

Khi thay \(z = 1\), ta thu được chính xác giá trị kỳ vọng của giai thừa giảm:

Như vậy, bài toán quy về việc tính \(P^{(j)}(1)\) cho mọi \(j \in [0, K]\).

3. Sử dụng Đạo hàm để khai triển Chuỗi lũy thừa

Đổi biến \(z = 1 + t\). Khi đó:

Chú ý rằng theo công thức Taylor, \(c_j = \frac{P^{(j)}(1)}{j!}\), do đó \(E[X^{\underline{j}}] = j! \cdot c_j\).

Để tính nhanh chuỗi \(C(t)\), lấy logarit tự nhiên hai vế:

trong đó \(S_j = \sum_{i=1}^N p_i^j\) là tổng lũy thừa cấp \(j\) của các xác suất \(p_i\).

Lấy đạo hàm hai vế mối quan hệ \(C(t) = \exp(Q(t))\), ta có:

Cân bằng hệ số của \(t^j\) ở hai vế, ta thu được công thức truy hồi tính các hệ số \(c_j\):

với \(b_j = \frac{(-1)^{j-1} S_j}{j}\).

4. Độ phức tạp tính toán

1. Tính \(S_j = \sum_{i=1}^N p_i^j\) với \(1 \le j \le K\): Tốn \(O(N \cdot K)\) phép tính.
2. Tính các hệ số \(b_j\) và \(c_j\) thông qua công thức truy hồi đạo hàm \(C'(t) = Q'(t)C(t)\): Tốn \(O(K^2)\).
3. Tính bảng số Stirling loại hai \(\left\{ \begin{matrix} K \\ j \end{matrix} \right\}\): Tốn \(O(K^2)\).
4. Tổng hợp đáp án \(E[X^K] = \sum_{j=0}^K \left\{ \begin{matrix} K \\ j \end{matrix} \right\} j! c_j \pmod{998244353}\): Tốn \(O(K)\).

Tổng độ phức tạp thời gian: \(\mathcal{O}(N \cdot K + K^2)\), hoàn toàn tối ưu và chạy trong khoảng \(0.2\) giây với \(N = 10^5, K = 2000\).