今回扱うのはyukicoder contest 360 F問題 No.2075 GCD Subsequenceです。公式解説はゼータ変換について既に熟知している人向けに書かれているためかゼータ変換絡みのキーワードが一切使われずに式変形がされており、ゼータ変換を知らない人が読んだ時にどうしてこのような変形が思いつくのか分からないかもしれません。
特に★3の解説は筆者のように★2～2.5を主戦場とする参加者もupsolve時に読むので、★3以上を主戦場とする上級者の方々にとっては前提知識となるキーワードでも略さずにちらつかせれば誰かの役に立つかもしれないかなと思い、ゼータ変換の言葉をきちんと使って検索しやすいようにまとめてみました。
問題の概要
正確な問題文はこちらです。色々すっ飛ばして解説を理解するためのエッセンスだけを抽出すると以下のような問題になります。
正整数$M,Q$と長さ$M$の整数列$B = (B_j)_{j=1}^{M} = (B_1,B_2,\ldots,B_M)$が与えられます。 以下で説明する$Q$個のクエリを与えられた順に処理してください。
各クエリは$M$以下の正整数$j$と整数$x$の組$(j,x)$として与えられます。 クエリ$(j,x)$を処理するには、まず$B_j$を$x$で置き換えることで$B$を更新し、その後
\[ \sum_{\textrm{gcd}(j,k) = 1} B_k \]
を求めてください。
元の問題文の原型を留めていませんが、$B$は公式解説で言うところの$\textrm{dp}$で、$Q$は$N$で、$j$は$A_i$です。
前置き
要求されているのは$B$の一点更新と、$M$以下の任意の正整数$j$に対する$\textrm{gcd}(j,k) = 1$となる$k$をわたる$B_k$の総和取得です。後者が見慣れない操作ですが、実はこれは倍数ゼータ変換と（その逆変換である倍数メビウス変換ではなく）約数メビウス変換の組み合わせで高速に処理できます。
ゼータ／メビウス変換が何かについては説明しないので、それらを知らない場合は調べてみましょう。この記事の目的はあくまで、検索しやすいキーワードを散りばめて解説の翻訳をすることです。
一点更新は倍数ゼータ変換で問題なく処理できるので、$M$以下の正整数$j$を固定した時の総和取得を倍数ゼータ変換でどう計算するかを説明します。
解説
$M$以下の各正整数$m$に対し$C_m := \sum_{\textrm{gcd}(j,k) = m} B_k$と定めると、求める値$\sum_{\textrm{gcd}(j,k) = 1} B_k$は$C_1$に他なりません。
整数列$(C_m)_{m=1}^{M}$を$C$と置きます。$C$は$B$の添字の動く範囲を、$\textrm{gcd}(j,-)$の値で類別することで分割して総和を取ったものです。一重和の添字の動く範囲を分割すると、一重和を二重和で表すことができたりして便利です。一般に集合$X,Y$と写像$f \colon X \to Y$が与えられた時、$f$による各点の逆像全体の集合$\{f^{-1}(y) \mid y \in Y\}$が$X$の（空かもしれない部分集合の族による）分割を与えます。これを$f$を用いた各点逆像による分割と呼ぶことにしましょう。
$B$と$C$の倍数ゼータ変換をそれぞれ$\zeta_{\textrm{mul}} * B = ((\zeta_{\textrm{mul}} * B)_m)_{m=1}^{M}$と$\zeta_{\textrm{mul}} * C = ((\zeta_{\textrm{mul}} * C)_m)_{m=1}^{M}$と置きます。ちなみに掛け算の記号で書いているのは、隣接代数を用いたゼータ変換の定義が実際に畳み込みで与えられるからです。
$M$以下の任意の正整数$m$に対し、倍数ゼータ変換の定義から
\[ (\zeta_{\textrm{mul}} * C)_m = \left\{ \begin{array}{ll} (\zeta_{\textrm{mul}} * B)_m & (m \mid j) \\
0 & (\textrm{otherwise}) \end{array} \right. \]
となります。何故なら$m$が$j$の約数である時、先程$B$から$C$を構成した際に説明した写像$\textrm{gcd}(j,-)$を制限すると$M$以下の$m$の倍数$k$全体の集合の間の写像を定めるので、その写像を用いた各点逆像による分割を考えれば$(\zeta_{\textrm{mul}} * C)_m$の定義式は単に$(\zeta_{\textrm{mul}} * B)_m$の定義式の和をまとめ直しただけのものとなるからです。
従って$\zeta_{\textrm{mul}} * B$と$\zeta_{\textrm{mul}} * C$の約数メビウス変換をそれぞれ$\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * B = ((\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * B)_m)_{m=1}^{M}$と$\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * C = ((\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * C)_m)_{m=1}^{M}$と置くと、
\[ (\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * B)_j = (\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * C)_j \]
が成り立ちます。何故なら、約数メビウス変換の$j$での値は$j$の各約数$m$における値のみから定まるからです。
更に$\zeta_{\textrm{mul}} * C$の倍数メビウス変換を$\mu_{\textrm{mul}} * \zeta_{\textrm{mul}} * C = ((\mu_{\textrm{mul}} * \zeta_{\textrm{mul}} * C)_m)_{m=1}^{M}$と置くと、メビウスの反転公式から倍数メビウス変換は倍数ゼータ変換の逆変換なので
\[ \mu_{\textrm{mul}} * \zeta_{\textrm{mul}} * C = C \]
が成り立ちます。特に$(\mu_{\textrm{mul}} * \zeta_{\textrm{mul}} * C)_1 = C_1$です。
そして倍数メビウス変換と約数メビウス変換の定義から、
\[ \begin{align} C_1 =& \ \ (\mu_{\textrm{mul}} * \zeta_{\textrm{mul}} * C)_1 = \sum_{1 \mid m} \mu(m) (\zeta_{\textrm{mul}} * C)_m = \sum_{m=1}^{M} \mu(m) (\zeta_{\textrm{mul}} * C)_m \\
=& \ \ \sum_{m | j} \mu(m) (\zeta_{\textrm{mul}} * C)_m = (\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * C)_j = (\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * B)_j \end{align} \]
となります。以上より、$(\mu_{\textrm{div}} * \zeta_{\textrm{mul}} * B)_j$を計算すれば良いことが分かりました。これが公式解説で説明されている計算方法です。
余談
倍数ゼータ変換と約数メビウス変換の組み合わせでこんなクエリ処理ができるのは面白いですね。一般化するとどのようなことが言えるでしょうか？ 一般化のアイデアは単純で、写像を用いた逆像による分割で、一重和の添字集合を分割して二重和に変形するだけです。
まず有限半順序集合$P$と（単位的でなくても良い）$\mathbb{Z}$代数$R$が与えられている時、隣接代数の一般論として$P$上の$R$値関数に対するゼータ変換とメビウス変換が定義されます。
特に$R$が$\mathbb{Z}$であり、$P$の下部集合が正整数の始切片であり、その順序$s \leq t$が倍数関係$t \mid s$で定義されている時は倍数ゼータ／メビウス変換、$s \leq t$が約数関係$s \mid t$で定義されている時は約数ゼータ／メビウス変換、と競技プログラミングで広く呼ばれていますね。
全体加算や一点取得を行わない場合は$R$への$\mathbb{Z}$作用を用いないので、$R$をただの（単位的でなくても良い）環としても良いです。環と$\mathbb{Z}$代数は代数的に等価ですが、計算量込みでは等価ではないことにご注意ください。
同様に全体乗算や畳み込み乗算を行わないならば積構造は不要なので、$R$を単なる$\mathbb{Z}$加群としても良いです。代数的には可換群と等価ですね。
ここで写像$f \colon P \to P$と部分写像$g \colon P \to P$と写像$r \colon P \to 2^{P}$と$s \in P$が以下の条件を満たすとします：
- $g$は定義域に$r(s) \in 2^{P}$を含む。
- $P$の順序に関して、$s$は$r(s)$の最大元である。
- $g(s)$を上界に持つ$P$の要素全体の集合を$R_s$と置き、$f$の$R_s$への制限を$f_s$と置くと、$f_s$は順序保存写像$R_s \to r(s)$である。
- $P$の順序に関して、$r(s)$の任意の要素$s’$に対し$g(s’)$が逆像$f_s^{-1}(s’)$の最大元である。（従って特に$f_s$は$r(s)$への全射である）
例えば$P$がmeet半束であり、$f(t)$が$t$によらない$j \in P$を用いて$j \land t$で定められており、$g$が恒等写像であり、$r$が入力を最大元とする始切片を返す写像である時、条件を満たします。
特に$P$が$M$以下の正整数の倍数関係で与えられる半順序集合で$s = 1$であり、$R$が$\mathbb{Z}$であり、$P$上の$R$値関数$F$が$B$で与えられる時、$f(t)=s$を満たす$R_s$の要素$t$全体を渡る$F(t)$の総和はまさに$C_1$に他なりません。
より一般に、$f,g,r,s$が上の条件を満たしさえすれば、$\zeta_{\textrm{mul}} * B$から$C_1$を求めた要領で、$P$上の$R$値関数$F$のゼータ変換に対して逆像$f^{-1}(s)$での$P$のメビウス関数による線形結合を考えることにより$f(t)=s$を満たす$R_s$の要素$t$全体を渡る$F(t)$の総和取得が可能です。
特に、$P$の順序を逆転させた半順序集合$P^{\textrm{op}}$のメビウス関数が$P$自体のメビウス関数の引数の左右を入れ替えただけのものと一致する時、$P$上のゼータ変換と$P^{\textrm{op}}$上のメビウス変換の合成として表されるわけです。実装上はそのようなきれいな意味付けにこだわる必要がないので、$P$上のゼータ変換と$P$上のメビウス関数による線形結合で計算すれば十分です。
そのような操作に対応した抽象ゼータ変換の実装例はこちらです。
自分用覚え書き
github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。
数式環境をくくる大括弧と数式環境内の中括弧や半角空白は半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。
arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。