結果
問題 | No.2136 Dice Calendar? |
ユーザー | CuriousFairy315 |
提出日時 | 2022-10-21 07:56:55 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,330 ms / 5,000 ms |
コード長 | 3,233 bytes |
コンパイル時間 | 4,487 ms |
コンパイル使用メモリ | 76,772 KB |
実行使用メモリ | 149,344 KB |
最終ジャッジ日時 | 2023-09-13 10:18:01 |
合計ジャッジ時間 | 17,075 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 143 ms
83,488 KB |
testcase_01 | AC | 143 ms
83,452 KB |
testcase_02 | AC | 188 ms
81,596 KB |
testcase_03 | AC | 145 ms
83,428 KB |
testcase_04 | AC | 142 ms
83,568 KB |
testcase_05 | AC | 155 ms
83,264 KB |
testcase_06 | AC | 153 ms
83,808 KB |
testcase_07 | AC | 162 ms
83,512 KB |
testcase_08 | AC | 180 ms
83,576 KB |
testcase_09 | AC | 185 ms
83,640 KB |
testcase_10 | AC | 189 ms
84,028 KB |
testcase_11 | AC | 207 ms
83,688 KB |
testcase_12 | AC | 226 ms
82,040 KB |
testcase_13 | AC | 209 ms
83,596 KB |
testcase_14 | AC | 238 ms
86,360 KB |
testcase_15 | AC | 345 ms
88,436 KB |
testcase_16 | AC | 382 ms
88,156 KB |
testcase_17 | AC | 347 ms
97,760 KB |
testcase_18 | AC | 596 ms
97,804 KB |
testcase_19 | AC | 700 ms
116,116 KB |
testcase_20 | AC | 791 ms
116,296 KB |
testcase_21 | AC | 971 ms
149,064 KB |
testcase_22 | AC | 1,126 ms
149,128 KB |
testcase_23 | AC | 1,330 ms
148,968 KB |
testcase_24 | AC | 173 ms
146,712 KB |
testcase_25 | AC | 251 ms
149,344 KB |
testcase_26 | AC | 1,226 ms
149,072 KB |
ソースコード
import java.util.BitSet; import java.util.Scanner; import java.util.function.IntConsumer; public class Main { public static void main(String[] args) { try (Scanner sc = new Scanner(System.in)) { int N = sc.nextInt(); int[][] S = new int[N][6]; for (int i = 0; i < N; ++i) for (int j = 0; j < 6; ++j) S[i][j] = sc.nextInt() - 1; final int MOD = 998_244_353; long[] factorial = new long[N + 1]; factorial[0] = 1; for (int i = 1; i < factorial.length; ++i) factorial[i] = factorial[i - 1] * i; BitSet set = new BitSet(1 << N + 9); // 64MB程度 IntStack now = new IntStack(3200000), next = new IntStack(3200000); now.add(0b111111111); // 初項M_0を求める for (int[] dice : S) { IntStack put = next; now.forEach(multiSet -> next(multiSet, dice, set, put)); // M_iからM_{i+1}を求める IntStack swap = now; now = next; next = swap; next.clear(); } int ans = 0; for (int i = 0; i < now.size; ++i) ans = (int) ((ans + multichoose(factorial, now.stack[i])) % MOD); System.out.println(ans); } } private static int[] deBrujin32 = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; public static int numberOfTrailingZeros(int i) { // 丁度1bit立っている値に対してその立っている位置を返す if (i == 0) return 32; return deBrujin32[i * 0x077CB531 >>> 27]; } public static long calcPartition(int multiSet) { // 与えられた多重集合に対して、立っているbitの位置を保持する数列Pを返す long partition = 0; for (int i = 5; i <= 45; i += 5) { int lob = multiSet & -multiSet; partition += 1L + numberOfTrailingZeros(lob) << i; multiSet -= lob; } return partition; } public static int getPartition(long partition, int index) { // multiSetでindex番目に立っているbitの位置を求める return (int) (partition >> 5 * index & 0b11111); } public static long multichoose(long[] factorial, int multiSet) { // multiSetで与えられた多重集合を並べてできる組合せ long partition = calcPartition(multiSet); long multichoose = factorial[getPartition(partition, 9) - 9]; for (int i = 0; i < 9; ++i) multichoose /= factorial[getPartition(partition, i + 1) - getPartition(partition, i) - 1]; return multichoose; } public static void next(int multiSet, int[] dice, BitSet set, IntStack stack) {// diceを追加したときにできる新たな多重集合のうち、新しく発見したものをstackに入れる long partition = calcPartition(multiSet); for (int result : dice) { int mask = (1 << getPartition(partition, result)) - 1; int next = (multiSet & ~mask) << 1 | multiSet & mask; if (!set.get(next)) { set.set(next); stack.add(next); } } } public static class IntStack { int[] stack; int size = 0; IntStack(int length) { stack = new int[length]; } void add(int value) { stack[size++] = value; } int peek() { return stack[size - 1]; } int poll() { return stack[--size]; } void forEach(IntConsumer f) { for (int i = 0; i < size; ++i) f.accept(stack[i]); } void clear() { size = 0; } } }