結果
問題 | No.1241 Eternal Tours |
ユーザー | 👑 hos.lyric |
提出日時 | 2020-09-06 15:14:44 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 923 ms / 6,000 ms |
コード長 | 3,606 bytes |
コンパイル時間 | 3,141 ms |
コンパイル使用メモリ | 80,832 KB |
実行使用メモリ | 84,008 KB |
最終ジャッジ日時 | 2024-11-29 11:05:30 |
合計ジャッジ時間 | 20,919 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 118 ms
54,092 KB |
testcase_01 | AC | 120 ms
54,052 KB |
testcase_02 | AC | 418 ms
71,340 KB |
testcase_03 | AC | 105 ms
52,352 KB |
testcase_04 | AC | 111 ms
53,284 KB |
testcase_05 | AC | 118 ms
53,964 KB |
testcase_06 | AC | 116 ms
54,032 KB |
testcase_07 | AC | 121 ms
53,952 KB |
testcase_08 | AC | 120 ms
54,240 KB |
testcase_09 | AC | 125 ms
54,200 KB |
testcase_10 | AC | 120 ms
53,980 KB |
testcase_11 | AC | 119 ms
53,964 KB |
testcase_12 | AC | 116 ms
54,104 KB |
testcase_13 | AC | 118 ms
54,064 KB |
testcase_14 | AC | 447 ms
66,496 KB |
testcase_15 | AC | 104 ms
54,116 KB |
testcase_16 | AC | 351 ms
62,260 KB |
testcase_17 | AC | 866 ms
82,092 KB |
testcase_18 | AC | 663 ms
75,580 KB |
testcase_19 | AC | 702 ms
71,224 KB |
testcase_20 | AC | 132 ms
53,364 KB |
testcase_21 | AC | 147 ms
54,072 KB |
testcase_22 | AC | 742 ms
79,424 KB |
testcase_23 | AC | 164 ms
54,368 KB |
testcase_24 | AC | 104 ms
53,124 KB |
testcase_25 | AC | 117 ms
54,232 KB |
testcase_26 | AC | 100 ms
52,692 KB |
testcase_27 | AC | 116 ms
54,120 KB |
testcase_28 | AC | 616 ms
71,328 KB |
testcase_29 | AC | 392 ms
71,364 KB |
testcase_30 | AC | 444 ms
71,324 KB |
testcase_31 | AC | 312 ms
64,188 KB |
testcase_32 | AC | 851 ms
81,804 KB |
testcase_33 | AC | 789 ms
72,544 KB |
testcase_34 | AC | 661 ms
71,380 KB |
testcase_35 | AC | 592 ms
71,280 KB |
testcase_36 | AC | 117 ms
53,776 KB |
testcase_37 | AC | 105 ms
53,104 KB |
testcase_38 | AC | 838 ms
72,568 KB |
testcase_39 | AC | 777 ms
70,120 KB |
testcase_40 | AC | 715 ms
71,332 KB |
testcase_41 | AC | 923 ms
84,008 KB |
testcase_42 | AC | 773 ms
70,136 KB |
testcase_43 | AC | 697 ms
71,380 KB |
ソースコード
import static java.lang.Math.*; import static java.math.BigInteger.*; import static java.util.Arrays.*; import static java.util.Collections.*; import java.math.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { new Main().run(); } Scanner in = new Scanner(System.in); void _out(Object...os) { System.out.println(deepToString(os)); } void _err(Object...os) { System.err.println(deepToString(os)); } final long MO = 998244353; final long G = 3; void run() { for (; in.hasNext(); ) { int X = in.nextInt(); int Y = in.nextInt(); long T = in.nextLong(); int A = in.nextInt(); int B = in.nextInt(); int C = in.nextInt(); int D = in.nextInt(); int m = 1 << (X + 1); int n = 1 << (Y + 1); long[] gms = new long[m]; long[] gns = new long[n]; gms[0] = 1; gns[0] = 1; gms[1] = power(G, (MO - 1) / m); gns[1] = power(G, (MO - 1) / n); for (int i = 2; i < m; ++i) { gms[i] = (gms[i - 1] * gms[1]) % MO; } for (int i = 2; i < n; ++i) { gns[i] = (gns[i - 1] * gns[1]) % MO; } long[][] f = new long[m][n]; f[0][0] = f[1][0] = f[0][1] = f[m - 1][0] = f[0][n - 1] = 1; for (int x = 0; x < m; ++x) { fft(n, gns, f[x]); } for (int y = 0; y < n; ++y) { long[] work = new long[m]; for (int x = 0; x < m; ++x) { work[x] = f[x][y]; } fft(m, gms, work); for (int x = 0; x < m; ++x) { f[x][y] = work[x]; } } long TT = 1 + (T - 1) % (MO - 1); for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) { f[x][y] = power(f[x][y], TT); } for (int i = 1; i < m - i; ++i) { long t = gms[i]; gms[i] = gms[m - i]; gms[m - i] = t; } for (int i = 1; i < n - i; ++i) { long t = gns[i]; gns[i] = gns[n - i]; gns[n - i] = t; } for (int x = 0; x < m; ++x) { fft(n, gns, f[x]); } for (int y = 0; y < n; ++y) { long[] work = new long[m]; for (int x = 0; x < m; ++x) { work[x] = f[x][y]; } fft(m, gms, work); for (int x = 0; x < m; ++x) { f[x][y] = work[x]; } } long invMN = power((1L * m * n) % MO, MO - 2); for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) { f[x][y] = (f[x][y] * invMN) % MO; } long ans = 0; for (int s : new int[]{+1, -1}) for (int t : new int[]{+1, -1}) { int dx = (s * C - A) & (m - 1); int dy = (t * D - B) & (n - 1); ans += s * t * f[dx][dy]; } ans = (ans % MO + MO) % MO; System.out.println(ans); } } long power(long a, long e) { if (e == 0) { return 1 % MO; } else { long b = power(a, e / 2); b = (b * b) % MO; if (e % 2 != 0) { b = (b * a) % MO; } return b; } } void fft(int n, long[] gs, long[] xs) { for (int l = n, shift = 0; (l /= 2) >= 1; ++shift) { for (int i = 0; i < l; ++i) { for (int j = i; j < n; j += l * 2) { long t = (xs[j] - xs[j + l]) % MO; xs[j] = (xs[j] + xs[j + l]) % MO; xs[j + l] = (gs[i << shift] * t) % MO; } } } for (int i = 0, j = 1; j < n; ++j) { for (int k = n / 2; k > (i ^= k); k /= 2) {} if (j < i) { long t = xs[i]; xs[i] = xs[j]; xs[j] = t; } } } }