結果
問題 | No.2582 Random Average^K |
ユーザー | uwi |
提出日時 | 2023-12-29 02:19:37 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 983 ms / 2,000 ms |
コード長 | 2,424 bytes |
コンパイル時間 | 3,720 ms |
コンパイル使用メモリ | 80,092 KB |
実行使用メモリ | 147,400 KB |
最終ジャッジ日時 | 2023-12-29 02:19:50 |
合計ジャッジ時間 | 12,262 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 126 ms
57,676 KB |
testcase_01 | AC | 126 ms
57,940 KB |
testcase_02 | AC | 131 ms
57,956 KB |
testcase_03 | AC | 126 ms
57,836 KB |
testcase_04 | AC | 126 ms
57,964 KB |
testcase_05 | AC | 126 ms
57,844 KB |
testcase_06 | AC | 136 ms
57,836 KB |
testcase_07 | AC | 132 ms
57,960 KB |
testcase_08 | AC | 138 ms
57,956 KB |
testcase_09 | AC | 448 ms
85,616 KB |
testcase_10 | AC | 700 ms
126,844 KB |
testcase_11 | AC | 611 ms
108,436 KB |
testcase_12 | AC | 980 ms
147,328 KB |
testcase_13 | AC | 515 ms
64,116 KB |
testcase_14 | AC | 535 ms
139,048 KB |
testcase_15 | AC | 983 ms
147,400 KB |
testcase_16 | AC | 795 ms
143,352 KB |
testcase_17 | AC | 803 ms
143,304 KB |
ソースコード
package no2xxx; import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class No2582 { static Scanner in; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(), K = ni(); final int mod = 998244353; int[][] fif = enumFIF(n+K+2, mod); // 1/1 + 1/2*x^1 + 1/6*x^2 + ... // (e^x-1)/x // (e^x-1)^n/x^n // e^(xi) のn+Kがわかればよい // i^t/t! // i^(n+K)/(n+K)! long ans = 0; for(int i = 0;i <= n;i++){ long c = C(n, i, mod, fif) * pow(mod-1, n-i, mod) % mod; ans += c * pow(i, n+K, mod); ans %= mod; } ans %= mod; ans = ans * fif[1][n+K] % mod; out.println(ans * fif[0][K] % mod * pow(invl(n, mod), K, mod) % mod); } public static long invl(long a, long mod) { long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p < 0 ? p + mod : p; } public static long C(int n, int r, int mod, int[][] fif) { if (n < 0 || r < 0 || r > n) return 0; return (long) fif[0][n] * fif[1][r] % mod * fif[1][n - r] % mod; } public static long pow(long a, long n, long mod) { // a %= mod; long ret = 1; int x = 63 - Long.numberOfLeadingZeros(n); for (; x >= 0; x--) { ret = ret * ret % mod; if (n << 63 - x < 0) ret = ret * a % mod; } return ret; } public static int[][] enumFIF(int n, int mod) { int[] f = new int[n + 1]; int[] invf = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; i++) { f[i] = (int) ((long) f[i - 1] * i % mod); } long a = f[n]; long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } invf[n] = (int) (p < 0 ? p + mod : p); for (int i = n - 1; i >= 0; i--) { invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod); } return new int[][]{f, invf}; } 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)); } }