noshi91のメモ

データ構造のある風景

みんぷろ2018決勝-A Uncommon Θ(Alog(log(A)))

A - Uncommon

これを  A := \max(a_i,m) として時間計算量  \Theta(A \log(\log(A) ) ) で解きます。

 \gcd 畳み込み

ゼータ変換・メビウス変換を理解する - Qiita
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ
添え字の  \gcd での畳み込みをおおまかに理解しているとします。  g(x) := \sum_{x|d} f(d) は行列  M を用いて  g = Mf と表現できます。 これを軸にして式変形を行います。

値の定義と記法

添え字は 1-indexed
アイバーソンの記法 - Wikipedia

  • 行列  M
     M_{i,j} := \lbrack i | j \rbrack
  • 単位ベクトル  e_i
     (e_i)_j := \lbrack i = j \rbrack
  • 入力  a を表すベクトル  v
     v_i := \# \lbrace j \mid a_j = i \rbrace
  • ベクトル同士の各点積  \circ
     (x \circ y)_i := x_i y_i
    演算子の優先度は行列積より低いとする

例えば、 \gcd 畳み込みは  M ^{-1}(Mx \circ My) となる。
また、 1 × N 行列と  N 次元ベクトルの同一視などを断りなく行う。

アルゴリズム

 i についての答えは以下のように書くことが出来る。
 (M^{-1}(Mv \circ Me_i) )_1
 \because  v e_i \gcd で畳み込みすれば、その第  1 成分は  \gcd(i, a_j) = 1 なる j の個数となる。
これを式変形すると
 = e_1^T(M^{-1}(Mv \circ Me_i) )
 = (e_1^T M^{-1})(Mv \circ Me_i)
 = ( (M^T)^{-1}e_1)^T (Mv \circ Me_i)
 = ( (M^T)^{-1}e_1 \circ Mv)^T(Me_i) \quad \because \  x^T(y \circ z) = (x \circ y)^T z
 = ( ( (M^T)^{-1}e_1 \circ Mv)^T M)e_i
よって  i に依存しない部分を新しく文字で置いて
 u := ( (M^T)^{-1}e_1 \circ Mv)^T M
とすれば、求める値は
 ue_i = u_i
となることが分かった。
すなわち  u の各成分を出力すればよい。

 M 及びその転置や逆行列とベクトルとの積を  \Theta(N \log (\log (N) ) ) で計算するアルゴリズムを用いれば、この問題を解くことが出来る。

実装例

Submission #9522125 - 「みんなのプロコン 2018」決勝
分かりやすさのため  \Theta(A \log(A) ) の実装になっています。
 Mv : {\rm multiple\_zeta}(v)
 vM : {\rm divisor\_zeta}(v)
 (M^T)^{-1}v : {\rm divisor\_mobius}(v)