AtCoder Beginner Contest 243 G問題 Sqrt
問題
提出解答
問題の概要
次を満たす長さ の列
の個数を求めよ.
に対して,
に対して,
である.
個のテストケース
制約
解法 1
まず, である.
なので,
とした
は
を意味する.
より, 「長さ
」は「長さ (可算) 無限」に置き換えても良い.
この置き換えにより, があたえられた場合の答え
を第
項目で場合分けすることにより,
となることがわかる. これを累積和を用いて実装すると, 時間計算量 となってしまい, 間に合わない.
解法 2
解法 1 では に着目していたが,
について着目する.
が固定されているとき,
として可能なのは
である. そして, は無限列としているので,
であるような整数列の数は
である.
また, について,
. つまり,
でなくてはならない. 以上から,
となり, 時間計算量 で求めることができる.
解法 3
今回, なので,
であるから, 解法1を用いて
を求め, 各問について,
ならば前計算の結果をそのまま答え,
ならば, 解法2を用いて
を求める方針を取れば, 1テストファイルあたりの時間計算量
で求めることができる.