ABC 428 G — Necklace

考察

回転で同じになる並べ方でも、何回回すと元に戻るかは列によって違う。そのため、順序付きの列数を単に長さで割ることはできない。各回転で変わらない列を数えて平均すれば、周期のある並べ方も正しく扱える。まず列を数えるDPを作り、回転の固定点計数へつなげよう。

長さと総積を状態にして、順序付きの列を数える

宝石は NN 種類あり、種類 ii の美しさを bib_i、求める総積の上限を UU とする。同じ美しさでも種類が違えば別の宝石であり、各種類は何個でも使える。すべて bi≥2b_i\geq 2 なので、長さ LL の列の総積は少なくとも 2L2^L である。従って調べる長さは

1≤L≤V,V=⌊log⁡2U⌋1\leq L\leq V,\qquad V=\lfloor\log_2 U\rfloor

に限られる。ただし種類数が大きいので、この短さだけでは全列を生成できない。長さと総積が同じ列は、その後に追加できる宝石も同じであることに注目してまとめる。

美しさ aa の宝石の種類数を freq[a]\mathrm{freq}[a] とし、An[s]A_n[s] を「長さ nn、総積 ss の順序付き宝石列の数」と定義する。範囲は 0≤n≤V0\leq n\leq V、1≤s≤U1\leq s\leq U である。空列の積は1とし、初期値は

A0[1]=1,A0[s]=0(2≤s≤U)A_0[1]=1,\qquad A_0[s]=0\quad(2\leq s\leq U)

とする。長さ nn の列の末尾に美しさ aa の宝石を加えると、総積は ss から sasa になる。この宝石には freq[a]\mathrm{freq}[a] 通りの種類の選び方があるので、遷移は

An+1[sa]+=An[s] freq[a]A_{n+1}[sa]\mathrel{+}=A_n[s]\,\mathrm{freq}[a]

である。遷移の条件は 2≤a2\leq a かつ sa≤Usa\leq U。n=0,1,…,V−1n=0,1,\ldots,V-1 の順に、更新先の配列を0で初期化してから全遷移を加える。以降、個数の加算・乗算は問題指定の素数 p=998244353p=998244353 を法として行う。

例えば美しさがともに2の二種類の宝石を A、B とすると、freq[2]=2\mathrm{freq}[2]=2 であり、A1[2]=2A_1[2]=2、A2[4]=4A_2[4]=4 となる。後者は AA、AB、BA、BB の4列である。美しさだけを一種類にまとめてしまうと、この区別が失われる。

一つの回転が固定する列は、巡回ごとに種類が一定

長さ LL の位置に 0,1,…,L−10,1,\ldots,L-1 と番号を付け、tt 個分の回転を「位置 jj を (j+t) mod L(j+t)\bmod L へ移す操作」とする。0≤t<L0\leq t<L の各回転について、繰り返し移動して元の位置へ戻るまでの位置の集まりを巡回と呼ぶ。

巡回数と各巡回の長さは、それぞれ

g=gcd⁡(L,t),d=Lgg=\gcd(L,t),\qquad d=\frac{L}{g}

である。実際、元へ戻る最小の正の移動回数は L∣dtL\mid dt を満たす d=L/gcd⁡(L,t)d=L/\gcd(L,t) であり、全 LL 位置が長さ dd の巡回 gg 本に分かれる。回転後も列が変わらないためには、各巡回内の宝石がすべて同じ種類でなければならない。

例えば L=6,t=2L=6,t=2 なら g=2,d=3g=2,d=3 であり、巡回は次の2本になる。

0 → 2 → 4 → 0
1 → 3 → 5 → 1

それぞれに宝石 A、B を置けば、元の列は ABABAB となる。代表宝石は2個であり、各代表を3回ずつ使う。ここで3は巡回長であって、代表列の長さではない。また固定点には AAAAAA のようにさらに短い周期を持つ列も含まれるので、「最小周期がちょうどいくつの列か」を数える必要はない。

一般に、各巡回を含まれる最小の位置番号で順序付け、一つずつ代表宝石を選ぶ。この順序付き代表列の長さは g=L/dg=L/d である。代表宝石の美しさを c1,…,cgc_1,\ldots,c_g、その総積を y=c1⋯cgy=c_1\cdots c_g とすると、元の列の総積 xx は

x=c1d⋯cgd=ydx=c_1^d\cdots c_g^d=y^d

になる。従って、この回転が固定する総積 xx の列数は、x=ydx=y^d を満たす整数 yy がある場合に AL/d[y]A_{L/d}[y]、ない場合に0となる。代表列を回転で同一視することはない。巡回は位置によって区別されているからである。

ここで、ある巡回に美しさ aa を割り当てる種類の選び方は freq[a]\mathrm{freq}[a] 通りであり、freq[a]d\mathrm{freq}[a]^d 通りではない。巡回内の dd 位置に別々の種類を選ぶと、回転で固定されなくなる。種類の多重度は代表列を数える AL/d[y]A_{L/d}[y] にすでに含まれている。

同じ巡回長の回転をまとめ、長さごとに平均する

φ(d)\varphi(d) を「1以上 dd 以下で dd と互いに素な整数の個数」とする。特に φ(1)=1\varphi(1)=1 である。d∣Ld\mid L に対し、巡回長が dd の回転は φ(d)\varphi(d) 個ある。d>1d>1 では t=(L/d)kt=(L/d)k と書けば条件は 0≤k<d0\leq k<d、gcd⁡(d,k)=1\gcd(d,k)=1 となり、d=1d=1 には何も動かさない回転 t=0t=0 が対応する。

総積 xx、長さ LL のネックレス数を FL(x)F_L(x) とする。Burnsideの補題により、全 LL 回転の固定点数を足して LL で割ると

FL(x)=1L∑d∣L, y≥2yd=xφ(d) AL/d[y]F_L(x)=\frac{1}{L} \sum_{\substack{d\mid L,\ y\geq 2\\y^d=x}} \varphi(d)\,A_{L/d}[y]

となる。求める答えは f(x)=∑L=1VFL(x)f(x)=\sum_{L=1}^{V}F_L(x) である。反転では同一視しないため、平均するのは回転だけである。

先ほどの A、B の例で総積4を考えると、長さは2しかない。恒等回転の固定点は4列、1個分の回転の固定点は AA、BB の2列なので、F2(4)=(4+2)/2=3F_2(4)=(4+2)/2=3。軌道は AA、ABとBA、BB の三つである。単に A2[4]/2A_2[4]/2 とすると、AA、BB の軌道が小さいことを補正できない。

整数の冪を作って答えへ加える

実装では各 xx の実数の根を求めるより、代表積 yy から x=ydx=y^d を作る方が確実である。代表列の長さを n=L/dn=L/d と置き直すと、加える項は次の形になる。

f(yd)+=φ(d) An[y] (nd)−1f(y^d)\mathrel{+}=\varphi(d)\,A_n[y]\,(nd)^{-1}

ただし nd≤Vnd\leq V かつ yd≤Uy^d\leq U とする。ここで (nd)−1(nd)^{-1} は法 pp における逆元である。具体的には次の順で処理する。

  1. 入力を読みながら freq\mathrm{freq} を作る。1≤d≤V1\leq d\leq V の φ(d)\varphi(d) と、1≤L≤V1\leq L\leq V の逆元を前計算し、答えの配列を0にする。
  2. 空列の初期値から長さごとのDPを進め、AnA_n を n=1,2,…,Vn=1,2,\ldots,V の順に求める。
  3. 各 AnA_n ができたら、代表積 y=2,3,…,Uy=2,3,\ldots,U を調べる。x=y,d=1x=y,d=1 から始め、nd≤Vnd\leq V かつ x≤Ux\leq U の間、上の項を f(x)f(x) に加える。その後 xx を yy 倍し、dd を1増やす。An[y]=0A_n[y]=0 の代表積は省略してよい。
  4. 全長の寄与を加え終えたら、f(2),…,f(U)f(2),\ldots,f(U) を出力する。

各 AnA_n は、その層の寄与を集計し、次の層を作った後は破棄できる。全層を保持する実装でも、現在層と次層だけを保持する実装でも、同じ式を計算できる。

典型の発動条件

Burnside の補題・Polya 数え上げ

回転などで同一視する配置を数えたいが、対称性の強い配置だけ軌道が小さくなるときに候補となる。全配置数を操作数で割る代わりに、各操作で不変な配置数を平均する。固定点数が位置の巡回構造だけで決まれば、同じ巡回構造を持つ操作をまとめられる。

積を状態にする DP

要素の追加で集約量が乗算され、総積の上限が小さいときに使える。同じ美しさの選択肢を頻度で圧縮しても、種類の数は遷移の重みとして残す。各要素が2以上なら、長さ軸も対数個に抑えられる。

約数・完全冪の列挙

巡回内の同一性によって代表値が何度も現れると、総積は代表積の冪になる。整数の根を近似する代わりに、底から冪を生成すれば完全冪の条件を厳密に扱える。

問題固有の要素

美しさの総積は巡回内の反復回数だけ冪になる一方、宝石の種類は巡回ごとに一度だけ選ぶ。この二つを分けると、順序付き列のDPを固定点計数へそのまま再利用できる。

また、bi≥2b_i\geq 2 は長さ上限の根拠である。美しさ1を許すと総積が増えないまま列を延ばせるため、この有限長のDPは成立しない。対称性だけでなく、集約量と制約の組合せを確認したい。

正当性

長さ別のDPは空列から始め、末尾の宝石を一つ取り除くと遷移元と最後の種類が一意に定まる。美しさが等しい別種類の選択も freq[a]\mathrm{freq}[a] で数えるので、An[s]A_n[s] は長さ nn、総積 ss の順序付き宝石列を過不足なく数える。

長さ LL、回転量 tt に対し、巡回数を g=gcd⁡(L,t)g=\gcd(L,t)、巡回長を d=L/gd=L/g とする。回転で不変な列と、番号順に並べた各巡回の代表宝石からなる長さ gg の列は一対一に対応する。代表列の総積を yy とすると元の総積は ydy^d であり、一つの巡回内では同じ種類を反復するため、その種類の選択は一度だけ数える。従って総積 xx の固定点数は、x=ydx=y^d を満たす整数 yy があるとき AL/d[y]A_{L/d}[y]、なければ0である。

同じ巡回長 dd の回転は φ(d)\varphi(d) 個なので、約数ごとの重み付き和は全回転の固定点数の和に等しい。ある回転軌道の大きさを rr とすると、その中の各列を固定する回転は L/rL/r 個あり、軌道全体の寄与は r(L/r)=Lr(L/r)=L になる。従って固定点数の和を LL で割ると、周期を持つ列の軌道も含めて一度ずつ数えられる。

回転は長さと総積を保つ。すべての宝石の美しさが2以上なので、可能な長さ 1≤L≤V1\leq L\leq V の和を取れば、各総積のネックレスを漏れなく数えられる。反転を作用へ含めないため、回転だけで一致しない裏返しの列は別の軌道に残る。

実装上の注意

  • L=1L=1 では恒等回転だけなので、F1(x)=A1[x]=freq[x]F_1(x)=A_1[x]=\mathrm{freq}[x]。空列 A0[1]A_0[1] はDPの出発点にだけ使い、ネックレスとしては集計しない。
  • x=ydx=y^d は整数で判定する。底から生成するときは、次の乗算の前に x≤⌊U/y⌋x\leq\lfloor U/y\rfloor を確認すれば、上限超過と整数のオーバーフローを同時に避けられる。例えば d=2d=2 なら8は寄与せず、9は y=3y=3 として寄与する。
  • 頻度を二乗・三乗するのは、独立な代表位置を増やすときだけである。同じ巡回内の反復回数に応じて増やさない。別の巡回には、美しさが同じ別種類を選んでもよい。
  • 1≤L≤V≤18<p1\leq L\leq V\leq 18<p なので、すべての除数 LL に逆元が存在する。法を取った値へ通常の整数除算を使わず、逆元を掛ける。剰余同士の乗算には64 bit整数を使い、積を取るたびに法を取る。
  • 例えば美しさが (2,3,4)(2,3,4) の三種類なら、時計回りの列 ABC と ACB は総積24でも回転では一致せず、別のネックレスである。反転までまとめる数え方へ変えない。

復習の核

  • 回転で割る前に、周期のある列だけ軌道が小さくならないか確認する。異なるなら固定点数の平均へ進む。
  • g=gcd⁡(L,t)g=\gcd(L,t) は代表宝石の数、d=L/gd=L/g は一つの代表の反復回数。位置を数個描けば、DPの長さと冪の指数を自分で復元できる。
  • 集約量が同じでも、選択肢が同じとは限らない。美しさの重複は頻度に残し、巡回内では同じ種類を共有する。

計算量と制約

時間

入力と頻度集計に O(N+U)O(N+U) 時間かかる。DP一層の遷移数は

∑s=1U(⌊Us⌋−1)=O(Ulog⁡U)\sum_{s=1}^{U}\left(\left\lfloor\frac{U}{s}\right\rfloor-1\right) =O(U\log U)

なので、全 VV 層で O(VUlog⁡U)O(VU\log U)。答えの集計では、各長さ nn と各代表積 yy について冪を高々 ⌊V/n⌋\lfloor V/n\rfloor 回進める。従って上界は O(U∑n=1V⌊V/n⌋)=O(UVlog⁡(V+1))O(U\sum_{n=1}^{V}\lfloor V/n\rfloor)=O(UV\log(V+1)) である。

φ\varphi は約数を調べても O(V2)O(V^2)、逆元は線形の漸化式で O(V)O(V) に前計算できる。出力は O(U)O(U)。V=⌊log⁡2U⌋V=\lfloor\log_2 U\rfloor を代入すると、総時間は O(N+Ulog⁡2U)O(N+U\log^2 U) となる。

空間

全層のDP表を保存する場合は O(UV)O(UV)。上記の手順で各層の寄与をすぐ集計すれば、DPの現在層・次層、頻度、答えの配列が O(U)O(U)、φ\varphi と逆元が O(V)O(V) なので、合計 O(U)O(U) 空間にできる。入力は頻度へ直接集計し、宝石列を保存しない。

制約との対応

公式制約は 1≤N≤5×1051\leq N\leq 5\times 10^5、2≤U≤5×1052\leq U\leq 5\times 10^5、2≤bi≤U2\leq b_i\leq U。時間制限は2秒、メモリ制限は1024 MiBである。U≤5×105<219U\leq 5\times 10^5<2^{19} より V≤18V\leq 18 となり、長さ別の積DPを扱える。頻度が大きくても種類を一つずつ遷移させず、O(N)O(N) の入力処理後は美しさごとに集約する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 群作用・軌道数え上げ

主題
  • 群作用・軌道数え上げ: 群作用の固定点数を群要素のcycle typeごとに数え、BurnsideまたはPólyaの平均でorbit数を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 群作用・軌道数え上げ

    補助タグ: 資源軸knapsack DP 法上の四則演算・高速累乗・逆元 素因数・約数分解

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

    学習の位置

    体系上の位置: 群作用・軌道数え上げ

    • 群作用の固定点数を群要素のcycle typeごとに数え、BurnsideまたはPólyaの平均でorbit数を求められる。

    先に読む単元:

    • 資源・容量DP — 最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。
    • 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。
    • 同値な状態を正規化する — 対称な状態を同一視できると探索やDPの状態数を減らせるため、同値類の標準形と不変量を先に定める。
    • 素因数分解と約数構造 — 初歩的な素因数分解を、指数vectorと約数格子へ条件を分解する道具として発展させる。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題