リンク

http://www.topcoder.com/stat?c=problem_statement&pm=12079

問題概要

整数集合Aの部分集合Sで、xor和がlimit以下になるものの個数を求めよ。

制約

|A|<=50, 0<=Aの要素<=10^15

状態

Accepted(Java)

ポイント

解き方

+ ... limit以下の数は、1のある位置の次から*が連続して出るようなパターンに分割できる。たとえば11011なら、
0****
10***
1100*
11010
11011
に分割できる。これでたとえば10***なら、下3桁はどんな値でも良くなるため、Aの全要素を3ビット右シフトした値の集合で、xor和が10になるような部分集合の個数を数えれば良い。xor和がちょうどvalになるような個数を数えれば良い問題になった。

シフト後の集合をA'とする。A'の要素を使ってvalが表現可能であれば2^(n-rank(A))通りであり、そうでなければ0となる。
表現可能かどうかは、A'の基底をとり、valに対し基底の大きい方からxorして0になるか判定すればよい。表現可能であれば、表現可能な数はすべて同数うまれるので、2^(n-rank(A))となる。rank(A)は基底の本数と考えて良い。

sample 2の場合、
0**
100
101
に分割でき、1234567からそれぞれのA'は
0001111 0
1234567 4
1234567 5
となる。当然どれも表現可能で、rankは1,3,3になるので、2^(7-1)+2^(7-3)+2^(7-3)=96となる。

コード

+ ...
import java.util.Arrays;
 
public class XorCards {
	public long numberOfWays(long[] number, long limit) {
		int n = number.length;
		int[] e = new int[60];
		Arrays.sort(number);
		for(int i = 0, j = n-1;i < j;i++,j--){
			long q = number[i]; number[i] = number[j]; number[j] = q;
		}
		long[][] bass = new long[60][];
		for(int d = 59;d >= 0;d--){
			long[] bas = new long[64];
			for(long x : number){
				x >>>= d;
				int h = 63-Long.numberOfLeadingZeros(x);
				while(x != 0){
					if(bas[h] != 0){
						x ^= bas[h];
						h = 63-Long.numberOfLeadingZeros(x);
					}else{
						bas[h] = x;
					}
				}
			}
 
			int rank = 0;
			for(int i = 0;i < 64;i++){
				if(bas[i] != 0){
					rank++;
				}
			}
			e[d] = rank;
			bass[d] = bas;
		}
 
		long ret = 0L;
		for(int d = 59;d >= 0;d--){
			if(limit<<63-d<0){
				if(hasSolution(limit>>>d&~1L, bass[d])){
					ret += 1L<<n-(e[d]);
				}
			}
		}
		if(hasSolution(limit, bass[0])){
			ret += 1L<<n-e[0];
		}
		return ret;
	}
 
	public static boolean hasSolution(long x, long[] bas)
	{
		int h = 63-Long.numberOfLeadingZeros(x);
		while(x != 0){
			if(bas[h] != 0){
				x ^= bas[h];
				h = 63-Long.numberOfLeadingZeros(x);
			}else{
				return false;
			}
		}
		return true;
	}
 
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
 
最終更新:2013年09月08日 14:17