公式解説ではimos法による解法が紹介されていますが、双対 Segment Treeや双対 Disjoint Sparse Tableを用いることによっても同様に問題を解くことができます。

それぞれのデータ構造の各ノードでは、長さ\(K\)の数列\(d=(d_1,d_2,\ldots,d_K)\)を持ちます。各ノードに関する区間更新では、最初の\(K\)項が\(d_1,\ldots,d_K\)であり先の漸化式によって定まるような数列を、そのノードが覆っている区間に足す操作を行います。

計算量は公式解説の解法に比べ真に悪くなりますが、実装はこちらのほうが考えることが少ないぶん楽だと思われます。

双対 Segment Treeによる実装(C++)