Subtask 1:

Gọi ~f[i][j]~ là số cách xây dựng ~i~ cái kẹo, và số lượng kẹo trong túi cuối cùng là ~j~.

Công thức chuyển trạng thái: ~f[i][j]~ = ~\sum_{k = 1,|j - k| <= d}^{m} f[i - j][k]~, với ý nghĩa ~k~ là số lượng kẹo trong túi ngay trước túi đang xét hiện tại.

Trường hợp cơ sở: ~f[i][i] = 1, (1 \le i \le m)~.

Subtask 2:

Với ràng buộc ~m = 2~. Ta thấy công thức QHĐ lúc này là:

~f[i][1] = f[i - 1][1] + f[i - 1][2]~.

~f[i][2] = f[i - 2][1] + f[i - 2][2]~.

Hay có thể viết là ~dp[i] = dp[i - 1] + dp[i - 2]~, với ~dp[i] = f[i][0] + f[i][1]~.

Với thuật toán QHĐ thông thường mất độ phức tạp là ~O(n)~, nhưng với độ phức tạp như vậy sẽ không vượt qua được giới hạn của đề bài. Ta có thể giảm độ phức tạp xuống ~O(log(n))~ thông qua kĩ thuật Nhân ma trận hoặc Khử nhân ma trận.

Subtask 3:

Kết hợp cả Subtask 1 và Subtask 2. Ta sẽ dùng kĩ thuật Nhân ma trận để giải quyết bài toán này.

Để giảm số chiều của mảng ~f~, ta có thể gọi ~dp[i * m + j] = f[i][j]~.

Như vậy, độ phức tạp cho cả bài toán là ~O(K^3*log(n))~, với ~K = m * m = 100~.