リンク
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