没問です.
可愛そうなのでサンプル問題として使ってあげることにしました.
問題原案:uni_kakurenbo
分割の方法は,正確に 通りありますから,これらを全て試すことはできません.
視点を変えて, 本目の中パスタを構成する小パスタを固定することを考えてみます.
左からみて 以上 以下の位置にある小パスタを用いて 本目の中パスタを構成するとします.
すると,その中パスタの長さ は一意に定まります.
が の約数でなければ,分割は明らかに不可能です.
また,中パスタの長さは全て等しくなくてはなりませんから, 本目の長さが決まれば,全てのその長さになるように他の中パスタを前から順番に構成していくことを試せます.
この操作で全ての小パスタを中パスタにすることができれば,そのときに限り可能です.
これは 時間で行うことができます.
約数の個数のオーダーを考えると,このアルゴリズム全体としての時間計算量は と見積れます.
なお, 約数の個数は,実際には よりもずっと少ないです.
解説:uni_kakurenbo