結果
| 問題 | No.3594 Subset OR |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-05 13:55:27 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 755 ms / 3,000 ms |
| + 828µs | |
| コード長 | 9,268 bytes |
| 記録 | |
| コンパイル時間 | 1,719 ms |
| コンパイル使用メモリ | 93,728 KB |
| 実行使用メモリ | 438,648 KB |
| 最終ジャッジ日時 | 2026-08-05 13:56:07 |
| 合計ジャッジ時間 | 37,565 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
// new Main().check();
pw.flush();
}
void run() {
int N = sc.nextInt();
int[] A = sc.nextInts(N);
long[] F = new long[1 << 24];
for (int a : A) {
F[a / 64] |= 1L << (a % 64);
}
long[] G = BooleanLattice.supsetOrZetaPacked(F, 30);
long ans = 0;
for (long v : G) {
ans += Long.bitCount(v);
}
pw.println(ans);
}
}
class BooleanLattice {
/**
* 真偽値関数を {@code long} 配列にビットパックした表現に対して、
* superset OR ゼータ変換を行う。
*
* <p>
* 入力は、{@code B} 要素集合の部分集合上の真偽値関数
* {@code f : {0, ..., 2^B - 1} -> {false, true}} を表す。
* 部分集合 {@code S} に対する値 {@code f(S)} は、次の位置に格納される。
* </p>
*
* <pre>
* word = S >>> 6
* bit = S & 63
* f(S) = ((a[word] >>> bit) & 1) != 0
* </pre>
*
* <p>
* {@code B < 6} の場合、配列の長さは {@code 1} であり、
* 下位 {@code 2^B} ビットのみが有効である。
* それより上位の未使用ビットは {@code 0} でなければならない。
* </p>
*
* <p>
* 返される配列は、各部分集合 {@code S} に対して
* </p>
*
* <pre>
* g(S) = OR { f(T) | S ⊆ T }
* </pre>
*
* <p>
* で定義される superset OR ゼータ変換 {@code g} を、
* 入力と同じビットパック形式で表したものである。
* 入力配列 {@code a} 自体は変更されない。
* </p>
*
* <p>
* 下位6次元は各 {@code long} 内のビット演算でまとめて処理し、
* それより上位の次元は {@code long} 配列上で通常の
* superset OR ゼータ変換を行う。
* </p>
*
* <p>
* 計算量は
* {@code O((B + 1) * 2^max(0, B - 6))} 時間、
* {@code O(2^max(0, B - 6))} 追加空間である。
* </p>
*
* @param a
* 真偽値関数をビットパックした配列。
* 長さは {@code max(1, 2^(B - 6))} でなければならない
* @param B
* 集合の要素数
* @return superset OR ゼータ変換後の真偽値関数を
ビットパックした新しい配列
* @throws IllegalArgumentException
* {@code B < 0} の場合、
* {@code a} の長さが不正な場合、
* または {@code B < 6} で未使用ビットに {@code 1} が含まれる場合
*/
public static long[] supsetOrZetaPacked(long[] a, int B) {
if (B < 0) {
throw new IllegalArgumentException("B must be at least 0");
}
int expectedLength = (B < 6) ? 1 : 1 << (B - 6);
if (a.length != expectedLength) {
throw new IllegalArgumentException("Array length must be " + expectedLength);
}
long[] b = a.clone();
if (B < 6) {
int numBits = 1 << B;
if (numBits < 64) {
long mask = ~((1L << numBits) - 1);
if ((b[0] & mask) != 0) {
throw new IllegalArgumentException("Out-of-bounds bits must be 0");
}
}
}
// Intra-word dimensions (0 to 5)
// B の次元数まで OR ゼータ変換を施す。
for (int s = 0; s < b.length; s++) {
long val = b[s];
// Dimension 0 (width = 1)
if (B > 0) {
long mask0 = 0b101010101010101010101010101010101010101010101010101010101010101L;
val |= (val >>> 1) & mask0;
}
// Dimension 1 (width = 2)
if (B > 1) {
long mask1 = 0b11001100110011001100110011001100110011001100110011001100110011L;
val |= (val >>> 2) & mask1;
}
// Dimension 2 (width = 4)
if (B > 2) {
long mask2 = 0b111100001111000011110000111100001111000011110000111100001111L;
val |= (val >>> 4) & mask2;
}
// Dimension 3 (width = 8)
if (B > 3) {
long mask3 = 0b11111111000000001111111100000000111111110000000011111111L;
val |= (val >>> 8) & mask3;
}
// Dimension 4 (width = 16)
if (B > 4) {
long mask4 = 0b111111111111111100000000000000001111111111111111L;
val |= (val >>> 16) & mask4;
}
// Dimension 5 (width = 32)
if (B > 5) {
long mask5 = 0b11111111111111111111111111111111L;
val |= (val >>> 32) & mask5;
}
b[s] = val;
}
// Inter-word dimensions (6 to B-1)
if (B > 6) {
int n = B - 6;
for (int i = 0; i < n; i++) {
int step = 1 << i;
for (int s = 0; s < (1 << n); s++) {
if ((s & step) == 0) {
b[s] |= b[s | step];
}
}
}
}
return b;
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
public int[] nextInts(int n) {
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = nextInt();
}
return a;
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
}
// --- Original Code ---
//
//
// import java.io.IOException;
// import java.util.Arrays;
// import java.util.HashSet;
// import java.util.Set;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.FenchelDuality;
// import library.util.Longs;
// import library.util.collections.ImplicitTreap;
// import library.util.collections.IntTreapMultiSet;
// import library.util.collections.LongTreapMultiSet;
// import library.util.poset.BooleanLattice;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// // new Main().check();
// pw.flush();
// MergeFiles.export();
// }
//
// void run() {
// int N=sc.nextInt();
// int[]A=sc.nextInts(N);
// long[]F=new long[1<<24];
// for (int a : A) {
// F[a/64]|=1L<<(a%64);
// }
// long[]G=BooleanLattice.supsetOrZetaPacked(F, 30);
// long ans=0;
// for (long v : G) {
// ans+=Long.bitCount(v);
// }
// pw.println(ans);
// }
//
//
//
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//