考察
非減少列は各値の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.
出典