誤差の合計が 以下なので、各項も を満たす。 かつ なので、取り得る音の高さは から までに収まる。この範囲の整数の個数は である。
を、最初の 項を決めたとき、誤差の合計が ちょうど で、最後の音の高さ が である数列の個数とする。、 の状態を保存する。
最初の音の高さは に固定されるので、その誤差は である。 ならば
と初期化し、それ以外の状態は とする。 ならば有効な数列は存在しないため、直ちに を出力してよい。
ここで とし、最後の音の高さを に決める。この項の誤差は なので、最初の 項の誤差の合計は でなければならない。直前の音の高さ は を満たす必要があるため、 のとき
となる。 の状態の値は である。
の順に、各誤差 と最後の音の高さ を調べ、上の範囲の を 直接列挙して 足し合わせればよい。すべての加算は で割った余りで計算する。
最終的な答えは
である。誤差がちょうど の状態だけを数えるのではなく、 以下のすべての状態を足し合わせる。
状態数は 個であり、各状態で直前の音の高さを最大 個調べる。したがって、時間計算量は
である。これは 要素数 × 音の高さの範囲 × 総誤差の範囲 × 隣り合う音の高さの差の範囲 に対応する。与えられた制約では、この遷移を直接計算できる。
各段階では直前の段階だけを使うので、配列は2層分だけ保存すればよい。空間計算量は である。音の高さ を配列の添字 に対応させればよい。
証明
最初の項は に一意に定まり、その誤差は である。したがって、 のときに とする初期化は、長さ の有効な数列をちょうど一度数える。 の場合、後続の項を決めても誤差の合計は減らないので、答えは である。
Solution written by GPT6
が正しいと仮定する。最後の音の高さが で、誤差の合計が である有効な数列から最後の項を取り除くと、誤差が で、最後の音の高さ が を満たす数列が残る。
逆に、このような数列の末尾に を付け加えると、隣り合う音の高さの差に関する条件を満たし、誤差の合計はちょうど となる。この2つの操作は互いに逆なので、遷移は有効な数列を漏れなく、重複なく数える。最後に の状態をすべて足し合わせれば、求める答えが得られる。
