考察
pair(i,j)について一致column数の偶奇だけが必要なので、columnごとの「同じ値groupに属するpair」という0/1寄与をXORで累積できる。N行分のparity vectorをbitsetとして同時更新する。
採用する候補: 各column・値groupのrow maskを作り、該当rowのparity bitsetへXORする
棄却する候補: 全row pairについてM列を比較する
O(N²M)=8×10^9比較となり時間制限に厳しい。
N個のdynamic bitset parityを0初期化する。各column kでA_{i,k}を値1…999ごとにrow bitmaskへまとめ、各groupの全row iについてparity[i]へgroup maskをXORする。最後に各iでj>iのset bit数をpopcountして合計する。
典型の発動条件
bitset高速化
発動条件: 同じboolean演算をN個の対象へ繰り返し、N≤2000でword並列化できる。
row集合を64bit blocksで表しXOR・popcountをまとめて行う。
parityのXOR集計
発動条件: 一致回数そのものではなく奇偶だけが判定条件である。
各columnの一致indicatorをaddition mod 2としてXOR累積する。
問題固有の要素
値ごとにpairを列挙する代わりにgroup maskをgroup内の各rowへXORすると、group内完全graphの隣接vectorをbit並列で生成できる。
別の問題へ持ち帰る視点: 同値class内全pair更新はclass bitmaskを各memberのbitsetへbroadcastできる。
正当性
column kで値vを持つrow集合mask_vを作ると、その集合内の任意pairだけ一致数parityがtoggleされる。各i∈mask_vについてparity[i] xor=mask_vとすれば、全column後のbit jが1 iff i,jの一致列数がoddになる。 64 pair判定を一machine wordで並列化し、O(MN²/word_size)の実用時間に落とせる。
実装上の注意
- diagonal(i,i)もM回toggleされ得るが必ず集計から除き、j>iだけ数える。columnごとのgroup maskは使い回す前にclearする。
復習の核
- Mの偶奇でdiagonalが変わる例、全行同一、全値distinct、同じpairが複数列一致する例を三重loopと比較する。
計算量と制約
時間
O(M(N+V)⌈N/w⌉+MN)、w=64、Vは列ごとに初期化する値マスク数。maskを必要な値だけ初期化すればV≤N。
空間
O((N+N_V)⌈N/w⌉)語。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2000; 1 \leq M \leq 2000; 1 \leq A_{i,j} \leq 999; All input values are integers.
出典