外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

尺取り法

webp ·

解説している問題 Another 7-5-3 Festival

SS の LL 文字目から RR 文字目までからなる部分文字列を [L,R][L,R] と表します。 また、ある文字列 XX を 1010 進法の整数として解釈した値を f(X)f(X) と表します。

求める答えは、0<f([l,r])≤K0 < f([l,r]) \le K なる (l,r) (1≤l≤r≤∣S∣)(l,r) \ (1 \le l \le r \le |S|) の数です。

これは、f([l,r])≤Kf([l,r]) \le K なる (l,r)(l,r) の数から f([l,r])=0f([l,r]) = 0 なる (l,r)(l,r) の数を引くことで求まるため、それぞれを尺取り法によって求めれば計算量 O(N)O(N) でこの問題を解くことができます。