回答編集履歴
2
ビット演算一般形
answer
CHANGED
|
@@ -28,4 +28,43 @@
|
|
|
28
28
|
for(auto e: B) std::cout<<e<<std::endl;
|
|
29
29
|
return 0;
|
|
30
30
|
}
|
|
31
|
+
```
|
|
32
|
+
Javaの方がなじみあるのでJavaで書いてみますね。
|
|
33
|
+
BigInteger使うと簡単なんだろうけど、C++に標準の多倍長整数型がないようなので、配列で頑張った
|
|
34
|
+
最後だけめんどくさかったのでBitSetに変換して出力
|
|
35
|
+
```java
|
|
36
|
+
import java.util.*;
|
|
37
|
+
|
|
38
|
+
public class Main {
|
|
39
|
+
public static void main(String[] args) {
|
|
40
|
+
try (Scanner s = new Scanner(System.in)) {
|
|
41
|
+
int n = s.nextInt();
|
|
42
|
+
int sum = 0;
|
|
43
|
+
int[] a = new int[n];
|
|
44
|
+
for (int i = 0; i < n; i++) {
|
|
45
|
+
a[i] = s.nextInt();
|
|
46
|
+
sum += a[i];
|
|
47
|
+
}
|
|
48
|
+
long[] bit = new long[(sum >> 6) + 1];
|
|
49
|
+
bit[0] = 1;
|
|
50
|
+
sum = 0;
|
|
51
|
+
|
|
52
|
+
for (int i = 0; i < n; i++) {
|
|
53
|
+
int shiftCell = a[i] >> 6;
|
|
54
|
+
int shiftBit = a[i] & 0x3f;
|
|
55
|
+
for (int j = (sum >> 6); j >= 0; j--) {
|
|
56
|
+
if (shiftBit != 0) {
|
|
57
|
+
long upper = bit[j] >>> (64 - shiftBit);
|
|
58
|
+
if (upper != 0) {
|
|
59
|
+
bit[j + shiftCell + 1] |= upper;
|
|
60
|
+
}
|
|
61
|
+
}
|
|
62
|
+
bit[j + shiftCell] |= bit[j] << shiftBit;
|
|
63
|
+
}
|
|
64
|
+
sum += a[i];
|
|
65
|
+
}
|
|
66
|
+
System.out.println(BitSet.valueOf(bit));
|
|
67
|
+
}
|
|
68
|
+
}
|
|
69
|
+
}
|
|
31
70
|
```
|
1
=が必要だった
answer
CHANGED
|
@@ -19,7 +19,7 @@
|
|
|
19
19
|
max += a;
|
|
20
20
|
}
|
|
21
21
|
|
|
22
|
-
for(int S = 0; S < max; S++) {
|
|
22
|
+
for(int S = 0; S <= max; S++) {
|
|
23
23
|
if(x & (1 << S)) {
|
|
24
24
|
B.insert(S);
|
|
25
25
|
}
|