TopCoder, Sinle Round Match 649, Division 1, Level 2 : XorSequence

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13249&rd=16313

問題概要

　整数列 と正整数 が与えられる．ここで， は 2 の冪乗であり， の要素は全て 未満である．
　今，一つの整数 を選んで， の各要素を とのビットごとの排他的論理和で写した数列 を考える（ここで，記号 は XOR を表す二項演算）．
　 の 2 つのインデックス であって， なるものの個数を最大化するように を選んだとき，そのようなインデックスのペアの総数を求めよ．
　なお， は特殊な方法で与えられる．
　

解法

　あからさまに 2 進数的な問題なので， については全て 2 進表記で考えます． の 2 要素の大小関係を決定付けるのは，2 要素の間で異なっている桁の内で最上位のものです．XOR の特性を考えると， に於いて 1 となっている桁は の変換の際に反転し．それ以外はそのまま写ります．つまり，元々一致している桁は変換しても一致していて，そうでない（元々異なっている）桁は変換後も異なっています．従って，ある 2 要素の大小関係を決定付ける桁の位置は が与えられた時点で確定しています．
　上位の桁の方が影響が大きいので， の各桁の値を上から決めていくと考えます，このとき，ある桁で大小関係が定まった 2 要素は，それより下の桁をどのように決めたとしても大小関係が反転することは無いので，それ以降は（大小関係に関して）関係が無くなります．つまり， のある桁を決めるときは，その桁によって大小関係が確定する要素たちについて，転倒しないものの数が多くなるように決定していけばよいということになります．
　これを実装するためには，ある桁に着目したときに新たに確定する，転倒しない要素の対をそれなりに速く数えられなければなりません．1 つの桁について考えているので要素が 0 または 1 しか無いということを利用すると，比較的楽にできます．具体的には，0 の数を数えながら列を先頭から走査し，各要素に対して

• ビットが立っていない -> 発見済みの 0 のカウントを 1 増やす
• ビットが立っている -> 転倒していない要素のカウントを，手前に出現した 0 の個数分増やす

のように処理すると要素数に対して線形時間で数えることができます．ある桁に於ける選択肢はビットを反転させるか，そのまま残すかなので両方試すことができます．これを，大小関係が未確定のグループそれぞれに対して実行することで，その桁に於ける最適な選択を求めることができます．
　実装では，現在の桁より上の桁が全て一致している要素を（順序を崩さず）それぞれ別の配列に格納しておくと扱い易いです．次の桁に進むときは，それぞれの配列の要素を，着目している桁の値によって新たな 2 つの配列に振り分けます．
　各グループの要素数の和は常に で，各桁での選択肢は全体を一括して反転するか，そのままにするかなので，各桁ごとに 時間で最適な選択がどちらであるかを求められます．2 進表記での桁数は なので，全ての桁に対して最適な選択を求める処理は， 時間で実行できます．

コード

using LL = long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;

#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back

class XorSequence
{
public:
	long long getmax( int N, int sz, int A0, int A1, int P, int Q, int R )
	{
		VI A( sz );
		A[0] = A0;
		A[1] = A1;
		REP( i, 2, sz )
		{
			A[i] = ( LL( A[ i - 2 ] ) * P + LL( A[ i - 1 ] ) * Q + R ) % N;
		}

		return solve( A, N >> 1 );
	}

	LL solve( VI &A, int N )
	{
		VVI cur( 1 ), next;
		cur[0] = move( A );

		LL res = 0;
		for ( ; N; N >>= 1 )
		{
			LL zero = 0, one = 0;

			FOR( ary, cur )
			{
				VI zeros, ones;

				zero += solve_part( ary, N,  0 );
				one += solve_part( ary, N, 1 );

				FOR( a, ary )
				{
					( a & N ? ones : zeros ).PB( a );
				}
				next.PB( zeros );
				next.PB( ones );
			}
			next.erase( remove_if( ALL( next ), bind( &VI::empty, _1 ) ), next.end() );

			res += max( zero, one );

			swap( cur, next );
			next.clear();
		}

		return res;
	}

	LL solve_part( const VI &as, const int N, const int inv )
	{
		LL res = 0, zeros = 0;
		FOR( a, as )
		{
			const int a2 = inv ? ~a : a;

			if ( a2 & N )
			{
				res += zeros;
			}
			else
			{
				++zeros;
			}
		}

		return res;
	}
};