ABC 288 Ex — A Nameless Counting Problem

考察

非減少列は各値のmultiplicityで一意に決まり、XORへ寄与するのは奇数回現れる値だけである。

まず順序制約を外した長さLの列で各要素0..M・総XOR Xとなる個数f(L)をbit digit DPで求め、その後multiplicity partitionを使ってdistinct値の個数g(L)へ変換できる。

最終列は、奇数multiplicityを持つ相異なる値を1個ずつ置いたstrictly increasing列に、任意の値のpairを追加して得られる。

採用する候補: bit DPでf(L)、奇偶block分割でdistinct ordered列g(L)、最後にpair追加の組合せを行う三段階の数え上げ。

値域M+1を列挙せず、XORのbit独立性・multiplicity parity・非減少順の一意性を順に分離できる。

棄却する候補: A_1≤…≤A_Nを保ちながら各要素をbit DPで同時構築する。

上位bitが同じ要素groupごとの順序状態が複雑になり、N個のtight状態だけでは圧縮できない。

棄却する候補: 0..Mの各値についてmultiplicityを0..Nから選ぶDP。

Mは最大2^30近く、値を1つずつ走査できない。

f(L)のbit DPでは、上位bitで既にM未満と確定した要素数jだけを状態にし、未確定要素の当該bit選択数とXのbit parityを二項係数で数える。

同じ値の出現位置を奇数size blockと偶数size blockへ分けると、XOR条件を担うのは奇数blockに割り当てる相異なる値だけになり、その個数を既計算のg(j)で表せる。

長さN-2iのdistinct odd値集合を選んだ後、追加するi個のpairはM+1種類への重複組合せC(M+i,i)で分配できる。

計算の三段階を、空列を含む係数表まで具体化する。

上限付きordered列 f(L)。 長さLを固定し、上位bitから、上限M未満が確定した位置数jを状態とする。初期はdp[0]=1、他0。現在のMのbitをm、Xのbitをeとし、未確定のL−j位置で1を置く個数をtとする。m=0ならt=0のみで新状態j'=j、m=1なら0≤t≤L−jでj'=L−t。位置の選び方はC(L−j,t)。既にlooseなj位置で1の個数の偶奇がpである割当数をQ(j,p)とすると、Q(0,0)=1,Q(0,1)=0、j>0ではQ(j,0)=Q(j,1)=2^{j−1}。XOR bitをeにするためp=e xor (t mod2)を選び、next[j']+=dp[j]·C(L−j,t)·Q(j,p)とする。30bit後の全jの和がf(L)。L=0ではf(0)=[X=0]となる。

奇偶サイズの無名block。 odd(i,j),even(i,j)は、ラベル付きi位置を、全blockサイズが奇数または偶数であるj個の非空blockへ分ける方法数。blockにはラベルを付けない。どちらもT(0,0)=1、i>0かつj=0、j>iなどの不可能状態は0。i>0では固定した最小位置を含むblockのサイズsを選ぶと、そのほかs−1位置はC(i−1,s−1)通り、残りはT(i−s,j−1)通りなので、

T(i,j)=Σ_{1≤s≤i, sの奇偶が指定と一致} C(i−1,s−1)T(i−s,j−1)。

最小位置を含むblockが一意だからj倍もj!も掛けない。iの昇順にこの和を計算すれば、各表はO(N³)。例えばodd(3,1)=1、odd(3,3)=1、even(4,2)=3であり、最後を6にするとblockにラベルを付けて二重計数している。

distinct列 g(L)への補正。 分割したblockは最小位置の昇順に並べる。この一意の並びへg(j)が数える相異なる値のordered列を割り当てれば、奇数blockの値割当を過不足なく数える。偶数blockにはそのj値と異なる相異なる値を使う。a=M+1−yが非負のとき、h(x,y)=Σ_{k=0}^x even(x,k)·(a)_k、(a)_k=a(a−1)…(a−k+1) とする。(a)_0=1、k>aなら0。y>M+1では値集合を選べないので、その補正項全体を0にする。

空列はg(0)=f(0)=[X=0]。L=1,…,Nを昇順に、

g(L)=f(L)−Σ_{i=0}^L C(L,i)Σ_{j=0}^{min(L−1,i)} odd(i,j)g(j)h(L−i,j)。

iは奇数blockに属する位置の総数、jはそのblock数。全singletonの分割だけはi=j=Lで、これが求めたいg(L)なので和から除く。他は必ずj<Lであり既知のgを使える。i=0,j=0も必要で、全値が偶数回ならX=0だけをg(0)が選別する。hの直接計算は全(x,y,k)でO(N³)でよく、奇偶分割表・補正と合わせても桁DPのO(30N³)以内。

最後に答え Σ_{i=0}^{floor(N/2)} g(N−2i)/(N−2i)!·C(M+i,i) を取る。g(L)/L!が奇数出現値の集合を、C(M+i,i)がM+1種類へi個のpairを分配する方法を数える。この二つから各値のmultiplicityが一意に決まり、非減少列へ戻る。

典型の発動条件

対称な複数要素のbit DP

発動条件: 複数のlabel付き値を同じ上限以下にし、XORだけを制約するとき。

上限未満確定要素の個数と当該bitの1のparityを二項係数で数える。

multiplicity parity分解

発動条件: 同値要素が相殺する演算としてXORを持つ列を数えるとき。

奇数回の値だけをcoreとし、偶数回分をpairとして分離する。

set partitionによる重複除去

発動条件: ordered列の値重複を、等値位置blockのsize条件ごとに分類するとき。

odd/even size block数とfalling factorialで割当を数え、distinct項を漸化的に抽出する。

重複組合せ

発動条件: 選んだ各種類へ合計i個の同一単位pairを追加するとき。

M+1 bucketへのpair分配をC(M+i,i)で数える。

問題固有の要素

順序制約は最後にmultisetを1通りの非減少列へ並べる段階で処理し、それ以前はlabel付き列としてXORと重複構造を数える方が対称性を使いやすい。

別の問題へ持ち帰る視点: 順序・値域・演算制約が絡む数え上げでは、いったんlabel付き対象を数え、distinct coreとmultiplicityを経由してcanonical順序へ戻す分解を検討する。

正当性

非減少列は各値の出現回数で一意に決まり、xorへ寄与するのは奇数回の値だけである。まず順序自由の列数f(L)を、Mとの比較確定数とxorの各bitのparityで数える。固定最小位置を含むblockを選ぶ漸化式は奇偶サイズの無名分割を一度ずつ数える。blockを最小位置順に並べてg(j)とfalling factorialによる相異なる値を割り当てるため、余分なblock階乗は不要。空列g(0)=[X=0]も含め、全singletonのg(L)以外は、少ない奇数block数の既知gと偶数blockへの値割当へ分解できるため、Lの昇順に差し引いてgを求められる。最終列は奇数出現値を一回ずつ置いた集合と、残りi個の同値pairの配分に一意に分かれる。g(N−2i)/(N−2i)!とC(M+i,i)の積を全iで足すと全列を一回ずつ数える。

実装上の注意

  • f(L)のbit DPでは、既にM未満の要素の当該bit割当はXOR parity別の通り数を使い、未確定要素はMのbitを超えない選択だけ許す。
  • g(0)=[X=0]と奇偶表T(0,0)=1を先に置く。g(L)はj<Lのみで補正し、g(L)=0となるL>M+1でも同じ計算を使える。falling factorialは利用可能種類数を超えたら0にし、負の種類数へ形式的に延長しない。mod減算を正規化する。
  • factorial inverseはL≤200なので存在し、C(M+i,i)はi!の逆元と連続するM+1..M+iの積でmod計算する。

復習の核

  • 小さいM,Nで列を全列挙し、各列を奇数multiplicityのdistinct coreと追加pairへ分解して、g(L)/L!とC(M+i,i)の役割を照合する。

計算量と制約

時間

O(BN³+N³)、B=30。固定Lの桁DPはO(BL²)、全LでO(BN³)。奇偶分割のサイズ和、hの直接前計算、全gの補正はそれぞれO(N³)。二項係数とQの表はO(N²)。

空間

O(N²)、組合せ・分割係数と一桁DP。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 200; 0 \leq M \lt 2^{30}; 0 \leq X \lt 2^{30}; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

A Nameless Counting Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 上限制約付き桁DP

主題
  • 上限制約付き桁DP: 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 上限制約付き桁DP

    補助タグ: 組合せ係数・数え上げ 集合上の包除原理

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

    学習の位置

    体系上の位置: 上限制約付き桁DP

    • 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題