M: Bit Cumulative Product

全体FA: kotatsugame_arigatou (55:55)

オンサイトFA kotatsugame_arigatou: (55:55)

AC: 15/53

原案: amesyu, writer: nyuminyusupe

問題概要

01列Aに対して f(A) = “Aの累積和の総積” とする。�f(A) = K となるAで、Aの長さが最小なもののうち辞書順最小なものを出力せよ。そのようなAが存在しないときは-1を出力せよ。

​

●　0 ≤ K ≤ 10¹⁸

考察

01列を構築してみる。

• 最初が0だとf(A) = 0なので1 <= KならA[0] = 1
• A = [1]から0か1を右に挿入するする時�f(A + [0]) = f(A) × sum(A), f(A + [1]) = f(A) × (sum(A) + 1)�が成り立つ。

×1な操作は無駄なので2 ≤ K ならば�Aのprefixは[1, 1]。すなわちA = [1, 1 …] と続く。

考察

総積なので f(任意のAのprefix) は f(A)の約数になる�例: f([1, 1, 0]) = 4, は f([1, 1, 0, 1]) = 12 の約数 �=> 考えるべき状態は ”f(A) = Kの約数” となるようなA

長さ最小、辞書順最小をどう達成しよう�=> Queue！

popした01列をAとして先にA + [0] を挿入、A + [1]を次に挿入を繰り返すとpopされるのは長さ最小、辞書順最小になっているのでf(A) = Kとなるものが来たら答えを出力。

簡潔な実装

K = 0 -> [0], K = 1 -> [1]

以下 2 ≤ K とする。

Queue = { [1, 1] } から始めてpopした要素をAとしたとき、

f(A) = K ならばAを出力して終了する。�Kをf(A + [0])で割ったあまりが0ならばQueueに挿入�Kをf(A + [1])で割ったあまりが0ならばQueueに挿入

をこの順に行う。 計算量O(?) これは見積もれていません

計算量

より細かな考察を行うとf(A), sum(A)をペアとして持ってBFSを行うと、f(A), sum(A) が既に訪れているならば枝刈りができる。(sum(A)が同じならばAに0を挿入しても同じ値が掛けられるので長さ、辞書順が覆ることはない)��sum(A)の上界は高々log Kであるため、頂点数はKの約数の個数をd(K)として d(K)log K となる。推移は高々2本であるため O(d(K)logK) で解けた。

計算量

実は約数を絡めなくても通る

• f(A) ≤ 10¹⁸ となるAは、最初の2項([1, 1]) が固定されていれば少ない。(12024238 ≒ 10⁷個)

​

WA!

• 10¹⁸ < 20! なので20ぐらいから割れるだけ割る
• BFSするとき、f(A)のみを持つ(sum(A)を持ち忘れる)