ABC 390 G — Permutation Concatenation

考察

連結した値を整数ごとの寄与に分けると、各整数が何倍されるかは、その右側に並ぶ整数の総桁数だけで決まる。右側の集合を選ぶ操作を生成関数へ写し、左右の並べ方を階乗で数える。同じ桁数の整数では、右側の選択から得られる重みを共有できる。

すべての順列を作る方針では N!N! 通りあり、N≤2×105N\leq 2\times 10^5 に対応できない。そこで、足し合わせる順序を交換し、一つの整数 mm が全順列へ与える寄与を先に求める。以後の係数や答えは、すべて法 998244353998244353 で計算する。

右側の個数と総桁数を分ける

整数 tt の十進表記の桁数を ℓ(t)\ell(t) とする。mm より右側に並ぶ整数の集合を SS とすると、連結値のうち mm に由来する部分は次の値である。

m 10∑t∈Sℓ(t)m\,10^{\sum_{t\in S}\ell(t)}

右側の並び順を変えても、この値は変わらない。さらに r=∣S∣r=|S| とすると、右側の並べ方は r!r! 通り、残る左側の並べ方は (N−1−r)!(N-1-r)! 通りである。つまり、必要なのは「右側を何個選んだか」と「選んだ集合の桁数による重み」であり、右側の順序そのものを状態に持つ必要はない。

各整数 tt について、右側に選ばなければ 11、選べば 10ℓ(t)x10^{\ell(t)}x を掛ける。この積では、xx の次数が選んだ個数、係数の10の冪が選んだ整数の総桁数を表す。例えば右側が {3,10}\{3,10\} なら、対応する項は 103x210^3x^2 である。次数2は右側の整数が2個という意味であり、総桁数3とは異なる。

同じ桁数の因子をまとめて作る

NN の桁数を BB とする。1≤b≤B1\leq b\leq B に対し、bb 桁の整数が現れる区間の両端と、その個数を定める。

Lb=10b−1,Ub=min⁡(N,10b−1),Cb=Ub−Lb+1\begin{aligned} L_b&=10^{b-1},\\ U_b&=\min(N,10^b-1),\\ C_b&=U_b-L_b+1 \end{aligned}

同じ桁数の整数は同じ一次因子を持つ。bb 桁の群から選ぶ集合の生成関数は、二項定理により次のように書ける。

Gb(x)=(1+10bx)Cb=∑r=0Cb(Cbr)10brxr\begin{aligned} G_b(x)&=(1+10^b x)^{C_b}\\ &=\sum_{r=0}^{C_b}\binom{C_b}{r}10^{br}x^r \end{aligned}

係数は、CbC_b 個から rr 個を選ぶ方法の数に、その総桁数 brbr による重みを掛けたものだ。階乗と逆階乗を NN まで前計算し、10br10^{br} は直前の値へ 10b10^b を掛けて更新すれば、GbG_b の全係数を O(Cb+1)O(C_b+1) 時間で作れる。

まず、まだどの整数も除いていない全体の積を一度だけ計算する。上付きの0は「除去前」を表す。

F0(x)=∏b=1BGb(x)=∑r=0NFr0xrF^0(x)=\prod_{b=1}^{B}G_b(x)=\sum_{r=0}^{N}F^0_r x^r

G1,G2,…,GBG_1,G_2,\ldots,G_B の順に、現在の積へ次の群をNTTによる畳み込みで掛ける。この順序なら、合成後の次数は min⁡(N,10b−1)\min(N,10^b-1) と幾何的に増え、最後に次数 NN となる。各群を二項係数から直接作ることと合わせて、合成全体は O(Nlog⁡N)O(N\log N) 時間に収まる。計算量節で最後の群も含めて評価する。

一次因子を係数の低い方から取り除く

mm が bb 桁なら、mm 自身を右側に選ばないよう、その一次因子を一つだけ除く。

Qb(x)=F0(x)1+10bx=∑r=0N−1qrxrQ_b(x)=\frac{F^0(x)}{1+10^b x}=\sum_{r=0}^{N-1}q_r x^r

ここで qrq_r は、mm 以外から右側の整数を rr 個選んだときの、10総桁数10^{\text{総桁数}} の総和となる。F0=(1+10bx)QbF^0=(1+10^b x)Q_b の定数項と rr 次係数を比べると、

q0=F00=1,Fr0=qr+10bqr−1(1≤r<N)\begin{aligned} q_0&=F^0_0=1,\\ F^0_r&=q_r+10^b q_{r-1}\quad(1\leq r<N) \end{aligned}

なので、更新式は次の形になる。

qr=Fr0−10bqr−1(1≤r<N)q_r=F^0_r-10^b q_{r-1}\quad(1\leq r<N)

低次から順に求めれば、直前の係数だけで次の係数が決まる。一般の多項式除算や逆数計算は不要で、各桁数につき O(N)O(N) 時間である。最高次の係数には FN0=10bqN−1F^0_N=10^b q_{N-1} が成り立つが、答えには q0,…,qN−1q_0,\ldots,q_{N-1} だけを使う。

集合の重みへ左右の並べ方を掛ける

固定した mm に対し、右側の集合と、左右それぞれの並び順を決めると、順列が一つに決まる。したがって bb 桁の整数一つ当たりに掛ける重みは、次の内積で求まる。

Wb=∑r=0N−1qr r!(N−1−r)!W_b=\sum_{r=0}^{N-1}q_r\,r!(N-1-r)!

例えば N=4,m=2N=4,m=2 とし、右側の集合を S={1,3}S=\{1,3\} に固定する。左側は4だけなので、対応する順列は (4,2,1,3)(4,2,1,3) と (4,2,3,1)(4,2,3,1) の2通り。どちらも mm の寄与は200であり、この集合は q2q_2 に100を加え、これへ m=2m=2 と 2!1!2!1! を掛けると、寄与の総和400を再現する。実際には q2q_2 が右側の集合3通りの重みを合わせるので q2=300q_2=300 となり、r=2r=2 の寄与は 2×300×2!1!=12002\times300\times2!1!=1200 である。

同じ bb 桁の整数なら、取り除く因子も残りの重み WbW_b も共通する。群内の整数の和を SbS_b とすると、求める答えは次の式で得られる。

Sb=(Lb+Ub)Cb2,答え=∑b=1BSbWb\begin{aligned} S_b&=\frac{(L_b+U_b)C_b}{2},\\ \text{答え}&=\sum_{b=1}^{B}S_bW_b \end{aligned}

実装では、階乗・逆階乗を前計算し、桁数の小さい順に群の多項式を作って全体積へ合成する。その後、各桁数について全体積から一次因子を除き、重みの内積と整数和を掛けて答えへ加える。

典型の発動条件

要素ごとの線形寄与分解

連結・配置の値が、各要素の寄与の和として表せるときに使う。全配置を作る前に、一要素を固定して、その寄与が依存する情報を調べる。この問題では右側の総桁数だけに依存するため、並び順の列挙を集合の選択と階乗へ分離できる。

category母関数と因子除去

一要素を除いた集合の生成関数を繰り返し求めるとき、除く要素が同じ因子を持つ群に分かれていれば、全体積からの因子除去を群ごとに共有できる。特に除去する因子が 1+ax1+ax なら、係数比較から一次の漸化式を作れる。

問題固有の要素

整数が 1,2,…,N1,2,\ldots,N と連続しているため、同じ桁数なら連結の重みが等しく、群内の個数と整数和を区間の両端から求められる。また、低い桁数から合成した次数は 9,99,999,…9,99,999,\ldots と増える。この構造が、群ごとの再利用と合成時間の評価の両方を支える。

要素が任意の整数列であっても桁数による集約は使えるが、各群の個数がこのように増えるとは限らない。今回の合成時間の証明を、そのまま持ち込むことはできない。

正当性

整数 mm を固定する。任意の順列から、mm より右側の集合 SS と左右それぞれの並び順を一意に取り出せる。逆に、それらを決めて左側、mm、右側の順に連結すれば元の順列を復元できる。従ってこの対応に漏れも重複もない。

mm が bb 桁なら、F0F^0 から 1+10bx1+10^b x を一つ除いた QbQ_b の展開は、mm 以外の各整数を右側に選ぶかどうかと一対一に対応する。xrx^r の係数 qrq_r は、∣S∣=r|S|=r のすべての集合について 10∑t∈Sℓ(t)10^{\sum_{t\in S}\ell(t)} を足した値である。係数比較による漸化式は、この商の各係数を低次から一意に復元する。

各集合に対して左右の並び順は r!(N−1−r)!r!(N-1-r)! 通りなので、mWbmW_b は全順列における mm の寄与の総和となる。同じ桁数の整数は同じ因子を除くため、これらを足した値は SbWbS_bW_b である。さらに全桁数について足せば、各順列の連結値を整数ごとの寄与に分けた全項をちょうど一度ずつ数える。

N=1N=1 の場合も、Q1=1Q_1=1、r=0r=0 の左右の並べ方は 0!0!=10!0!=1 なので、答え1を返す。

実装上の注意

  • 各桁群は両端を含む区間 [Lb,Ub][L_b,U_b] とする。Ub=min⁡(N,10b−1)U_b=\min(N,10^b-1) であり、次の桁数の最初の整数を混ぜない。境界での個数と整数和は次の表のようになる。
NN個数(桁数順)整数和(桁数順)
111
9945
109, 145, 10
999, 9045, 4905
1009, 90, 145, 4905, 100
  • SbS_b を通常の整数で求めるなら、乗算前に64 bit整数へ変換して2で割り、最後に剰余を取る。法上で求めるなら2の逆元を掛ける。
  • 桁数ごとの除去では、毎回同じ除去前の F0F^0 を使う。別の桁数で因子を除いた配列を次の除去元にしない。減算後の剰余を正規化する。
  • 使う係数は 0≤r<N0\leq r<N。空集合と空の並び順も数えるため、階乗の初期値を 0!=10!=1 とする。

復習の核

  • 同じ桁なら、除去する因子も残りの重みも共有できる。一要素を除く計算を繰り返す前に、どの要素が同じ因子を持つかを調べる。
  • 生成関数の次数に何を数えさせるかを先に決める。ここでは右側の個数を次数に持ち、総桁数は係数の重みに埋め込む。
  • 畳み込みの回数だけでなく、各段で扱う次数の総量を見る。桁数の小さい群から合成することが、今回の計算量を支える。

計算量と制約

時間

次数の和が dd の二多項式をNTTで掛ける費用を M(d)=O((d+1)log⁡(d+2))M(d)=O((d+1)\log(d+2)) とする。bb 桁以下の群を合成した積の次数は、

Db=∑k=1bCk=min⁡(N,10b−1)D_b=\sum_{k=1}^{b}C_k=\min(N,10^b-1)

である。最後の段より前は Db=10b−1D_b=10^b-1、最後は DB=ND_B=N なので、

∑b=1BDb=N+∑b=1B−1(10b−1)≤N+10B−109=O(N)\begin{aligned} \sum_{b=1}^{B}D_b &=N+\sum_{b=1}^{B-1}(10^b-1)\\ &\leq N+\frac{10^B-10}{9}\\ &=O(N) \end{aligned}

となる。最後の評価には 10B−1≤N10^{B-1}\leq N を使った。最後の群が少数で、直前の段から次数がほとんど増えない場合も、この一段を NN として含めている。従って、各段の対数を O(log⁡(N+1))O(\log(N+1)) で押さえると、畳み込み全体の費用は次のとおりである。

∑b=2BM(Db)=O(Nlog⁡(N+1))\sum_{b=2}^{B}M(D_b)=O(N\log(N+1))

一般の NN 本の一次因子を均等に分けて掛ける積木では、各段に同程度の総次数があり、通常 O(Nlog⁡2N)O(N\log^2N) と評価する。今回は、同じ因子の冪を二項係数から直接作り、桁数の小さい群から順に合成するため、上の次数の和で評価できる。

階乗・逆階乗の前計算と全群の係数構築は O(N)O(N)、一次因子の除去と重みの内積は全 BB 群で O(NB)O(NB) かかる。B=⌊log⁡10N⌋+1B=\lfloor\log_{10}N\rfloor+1 より、全体は O(Nlog⁡(N+1)+NB)O(N\log(N+1)+NB)、N≥2N\geq2 では O(Nlog⁡N)O(N\log N) 時間である。N=1N=1 は定数時間となる。

空間

O(N)O(N)。階乗・逆階乗、現在の積、次の群の係数とNTTの作業領域を保持する。合成済みの古い積や処理済みの商をすべて保存せず、桁数ごとに領域を再利用する。

制約との対応

公式制約は 1≤N≤2×1051\leq N\leq2\times10^5、法は 998244353998244353、制限時間は2秒、メモリ制限は1024 MiBである。桁数は最大6種類なので、一次因子の除去と内積は高々6回の線形走査で済む。階乗の添字は法未満で逆階乗を作れ、次数 NN の積に必要なNTT長は最大 2182^{18} であり、この法で扱える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Permutation Concatenation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 組合せを生成関数へ符号化する

主題
追加で学ぶ技能
既習技能

主タグ: 畳み込み・相互相関 生成関数による組合せ構造の符号化

補助タグ: 組合せ係数・数え上げ 寄与の数え上げと順序交換

執筆: abc-explanation-author1.1.1 / revision 2

学習の位置

体系上の位置: 組合せを生成関数へ符号化する

  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。
  • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。

先に読む単元:

この解説で扱わないこと:

  • 係数列同士を単に畳み込む相互相関、および係数の組合せ的意味を持たない信号処理。

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題