\(A,T\) が与えられたときの \(f(A,T)\) の値について考えます． ここで，\(z_i=A_i+T \times x_i\) とします． 辞書順最大の \(x\) について，\(A_1 - T < z_i \leq A_1\) を満たす \(i>1\) は存在しません． もしそのような \(i\) が存在した場合，そのようなものの中で最小の \(i\) をとると，\(x_i\) の値をより大きくすることが可能だからです．

そこで，辞書順最大の \(x_1,x_2\cdots,x_N\) から，以下の手順で列 \(x'_1,x'_2,\cdots,x'_{N-1}\) を得ることを考えます．

• \(A_1<z_{i+1}\) なら \(x'_i=x_{i+1}-1\)，そうでないなら \(x'_i=x_{i+1}\)

このとき，列 \(x'\) は，\((A_2,A_3,\cdots,A_N)\) に対して，問題文中の条件を満たす列になっています．また逆に，\((A_2,A_3,\cdots,A_N)\) に対して条件を満たす列 \(x'\) があれば，そこから \(x\) を得ることもできます． さらに，\(x\) が辞書順最大であることは，\(x'\) が辞書順最大であることと同値です． これで，\(f(A,T)\) の値を \(f((A_2,A_3,\cdots,A_N),T)\) から計算できるようになりました．

\(f(A,T)\) の末尾の要素を \(g(A,T)\)と表記します． \(g(A,T)\) の値がどうなるか考えてみます． するとこれは， \(g((A_2,A_3,\cdots,A_N),T),A_1,A_N\) にのみ依存することがわかります． よって，\(A_N\) の値を決め打つと，各 \(i,j\) について，\(g((A_i,\cdots,A_N),T)=j\) となる\((A_i,\cdots,A_N)\) の数，というのを DP で求めることができます．

同様に，\(f(A,T)\) の \(1,2,\cdots,N-1\) 項目の値の分布も求められます． 計算量は全体で \(O(N^3K^2)\) になります．