結果
問題 |
No.2846 Birthday Cake
|
ユーザー |
|
提出日時 | 2024-08-29 13:52:37 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,924 bytes |
コンパイル時間 | 5,538 ms |
コンパイル使用メモリ | 88,276 KB |
実行使用メモリ | 87,736 KB |
最終ジャッジ日時 | 2024-08-29 13:53:24 |
合計ジャッジ時間 | 10,491 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 25 WA * 1 TLE * 8 |
ソースコード
package no2xxx; import java.io.PrintWriter; import java.util.*; public class No2846 { static Scanner in; static PrintWriter out; static String INPUT = ""; static void solve() { int K = ni(), n = ni(); Map<Long, long[]> dp = new HashMap<>(); Map<Long, Long> nums = new HashMap<>(); dp.put(1L, new long[]{0, 1}); nums.put(1L, 1L); for(int i = 0;i < K;i++){ Map<Long, long[]> ndp = new HashMap<>(); Map<Long, Long> nnums = new HashMap<>(); for(long key : dp.keySet()){ long[] f = dp.get(key); for(int j = n;j >= 1;j--) { if(j == 23 || j == 19 || j == 17 || j == 13)continue; long[] nf = add(f, new long[]{1, j}); if (nf[0] > nf[1]) break; ndp.put(h(nf), nf); nnums.merge(h(nf), nums.get(key), Long::sum); } } dp = ndp; nums = nnums; } long ans = nums.getOrDefault(h(new long[]{1, 1}), 0L); if(n == K && (n == 13 || n == 17 || n == 19 || n == 23))ans++; out.println(ans); } static long h(long[] a) { long ret = 0; for(long v : a)ret = ret * 1000000009 + v; return ret; } public static long[] reduce(long[] f) { if(f[1] == 0) { // n/0 f[0] = 1; }else if(f[0] == 0) { // 0/n f[1] = 1; }else { if(f[1] < 0) { // -a/-b ->a/b f[0] = -f[0]; f[1] = -f[1]; } long a = Math.abs(f[0]), b = f[1]; while (b > 0) { long c = a; a = b; b = c % b; } f[0] /= a; f[1] /= a; } return f; } public static long[] add(long[] a, long[] b){ return reduce(new long[]{a[0]*b[1]+a[1]*b[0], a[1]*b[1]}); } public static long[] sub(long[] a, long[] b){ return reduce(new long[]{a[0]*b[1]-a[1]*b[0], a[1]*b[1]}); } public static long[] mul(long[] a, long[] b){ return reduce(new long[]{a[0]*b[0], a[1]*b[1]}); } public static long[] div(long[] a, long[] b){ return reduce(new long[]{a[0]*b[1], a[1]*b[0]}); } public static int compare(long[] a, long[] b){return Long.signum(a[0] * b[1] - a[1] * b[0]);} public static long[] min(long[] a, long[] b){ return compare(a, b) <= 0 ? a : b; } public static long[] max(long[] a, long[] b){ return compare(a, b) >= 0 ? a : b; } public static int lowerBound(long[][] es, int p, long[] r) { int low = -1, high = p; while(high-low > 1){ int h = high+low>>>1; if(Long.compare(r[0]*es[h][1], r[1]*es[h][0]) <= 0){ high = h; }else{ low = h; } } return high; } public static Comparator<long[]> comp = (a, b) -> Long.signum(a[0]*b[1]-a[1]*b[0]); public static void main(String[] args) throws Exception { in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT); out = new PrintWriter(System.out); solve(); out.flush(); } static int ni() { return Integer.parseInt(in.next()); } static long nl() { return Long.parseLong(in.next()); } static double nd() { return Double.parseDouble(in.next()); } static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }