Editorial for Đếm dãy số

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Dễ dàng nhận thấy rằng mọi dãy số thỏa mãn đều không vượt quá $N=\lceil \frac{S}{3} \rceil$ ~N=\lceil \frac{S}{3} \rceil~ phần tử.

Gọi $dp[i][j]$ ~dp[i][j]~ $(1 \le i \le N$ ~(1 \le i \le N~, $0 \le j \le S)$ ~0 \le j \le S)~ là số dãy số độ dài $i$ ~i~ với tổng các phần tử bằng $j$ ~j~. Khi đó:

$dp[i][0]=1$ ~dp[i][0]=1~ với mọi $1 \le i \le N$ ~1 \le i \le N~.
$dp[1][j]=1$ ~dp[1][j]=1~ với mọi $3 \le j \le S$ ~3 \le j \le S~.
$dp[i][j]= \displaystyle \sum_{k=3}^{j}dp[i-1][j-k]$ với mọi $2 \le i \le N$ ~2 \le i \le N~, $3 \le j \le S$ ~3 \le j \le S~.

Ta có thể dễ dàng tính mảng $dp$ ~dp~ với độ phức tạp $O(S^3)$ ~O(S^3)~.

Nhận xét rằng việc tính toán $dp[i][j]$ ~dp[i][j]~ chỉ cần dựa trên các $dp[i-1][k]$ ~dp[i-1][k]~ với $3 \le k \le S$ ~3 \le k \le S~, nên ta có thể sử dụng Prefix Sum để tối ưu hóa.

Độ phức tạp: $O(S^2)$ ~O(S^2)~.

Editorial for Đếm dãy số

Comments