結果
問題 | No.1958 Bit Game |
ユーザー | tenten |
提出日時 | 2022-05-31 14:42:45 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 622 ms / 2,000 ms |
コード長 | 2,958 bytes |
コンパイル時間 | 3,795 ms |
コンパイル使用メモリ | 77,980 KB |
実行使用メモリ | 69,948 KB |
最終ジャッジ日時 | 2023-10-21 00:38:19 |
合計ジャッジ時間 | 19,576 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 523 ms
69,300 KB |
testcase_01 | AC | 505 ms
69,200 KB |
testcase_02 | AC | 622 ms
69,948 KB |
testcase_03 | AC | 539 ms
68,952 KB |
testcase_04 | AC | 547 ms
69,244 KB |
testcase_05 | AC | 532 ms
69,336 KB |
testcase_06 | AC | 544 ms
69,576 KB |
testcase_07 | AC | 545 ms
69,156 KB |
testcase_08 | AC | 533 ms
69,276 KB |
testcase_09 | AC | 548 ms
69,140 KB |
testcase_10 | AC | 275 ms
60,640 KB |
testcase_11 | AC | 378 ms
60,528 KB |
testcase_12 | AC | 474 ms
63,824 KB |
testcase_13 | AC | 407 ms
64,168 KB |
testcase_14 | AC | 368 ms
60,464 KB |
testcase_15 | AC | 471 ms
64,644 KB |
testcase_16 | AC | 383 ms
60,488 KB |
testcase_17 | AC | 472 ms
65,824 KB |
testcase_18 | AC | 483 ms
64,704 KB |
testcase_19 | AC | 409 ms
62,512 KB |
testcase_20 | AC | 402 ms
62,476 KB |
testcase_21 | AC | 472 ms
62,624 KB |
testcase_22 | AC | 233 ms
59,096 KB |
testcase_23 | AC | 360 ms
62,416 KB |
testcase_24 | AC | 476 ms
65,952 KB |
testcase_25 | AC | 356 ms
60,472 KB |
testcase_26 | AC | 357 ms
62,448 KB |
testcase_27 | AC | 453 ms
62,388 KB |
testcase_28 | AC | 420 ms
63,600 KB |
testcase_29 | AC | 316 ms
60,232 KB |
testcase_30 | AC | 60 ms
52,460 KB |
testcase_31 | AC | 62 ms
53,496 KB |
testcase_32 | AC | 60 ms
53,512 KB |
ソースコード
import java.io.*; import java.util.*; public class Main { static final int MOD = 998244353; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(); int n = sc.nextInt(); long x = sc.nextInt(); long y = sc.nextInt(); long[] countsX = new long[19]; for (int i = 0; i < x; i++) { int v = sc.nextInt(); for (int j = 0; j <= 18 && v > 0; j++) { countsX[j] += v % 2; v >>= 1; } } long[] countsY = new long[19]; for (int i = 0; i < y; i++) { int v = sc.nextInt(); for (int j = 0; j <= 18 && v > 0; j++) { countsY[j] += v % 2; v >>= 1; } } long ans = 0; for (int i = 0; i <= 18; i++) { long[][][] matrix = new long[19][2][2]; matrix[0][0][0] = (x * y - countsX[i] * countsY[i]) % MOD; matrix[0][0][1] = x * (y - countsY[i]) % MOD; matrix[0][1][0] = countsX[i] * countsY[i] % MOD; matrix[0][1][1] = x * countsY[i] % MOD; for (int j = 1; j <= 18; j++) { for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { for (int c = 0; c < 2; c++) { matrix[j][a][c] += matrix[j - 1][a][b] * matrix[j - 1][b][c] % MOD; matrix[j][a][c] %= MOD; } } } } long[] current = new long[2]; current[0] = (1 << i); int z = n; for (int j = 18; j >= 0; j--) { if (z >= (1 << j)) { z -= (1 << j); long[] next = new long[2]; for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { next[a] += matrix[j][a][b] * current[b] % MOD; next[a] %= MOD; } } current = next; } } ans += current[1]; ans %= MOD; } System.out.println(ans); } } class Scanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); public Scanner() throws Exception { } public int nextInt() throws Exception { return Integer.parseInt(next()); } public long nextLong() throws Exception { return Long.parseLong(next()); } public double nextDouble() throws Exception { return Double.parseDouble(next()); } public String next() throws Exception { if (!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } }