結果
問題 | No.2530 Yellow Cards |
ユーザー |
![]() |
提出日時 | 2023-11-03 22:16:15 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 556 ms / 2,000 ms |
コード長 | 1,185 bytes |
コンパイル時間 | 2,248 ms |
コンパイル使用メモリ | 76,736 KB |
実行使用メモリ | 137,224 KB |
最終ジャッジ日時 | 2024-09-25 20:40:21 |
合計ジャッジ時間 | 10,851 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 17 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");int n = Integer.parseInt(sa[0]);int k = Integer.parseInt(sa[1]);br.close();int mod = 998244353;long ni = modinv(n, mod);int k2 = k / 2;long[][] dp = new long[k + 1][k2 + 2];dp[0][0] = 1;for (int i = 0; i < k; i++) {int end = i / 2;for (int j = 0; j <= end; j++) {int j1 = i - j * 2;dp[i + 1][j + 1] += dp[i][j] * j1 % mod * ni % mod;dp[i + 1][j] += dp[i][j] * (n - j1) % mod * ni % mod;dp[i + 1][j] %= mod;}dp[i + 1][end + 1] %= mod;}long ans = 0;for (int i = 0; i <= k2; i++) {ans += dp[k][i] * (n + i) % mod;}ans %= mod;System.out.println(ans);}static long modinv(long a, int m) {long b = m;long u = 1;long v = 0;long tmp = 0;while (b > 0) {long t = a / b;a -= t * b;tmp = a;a = b;b = tmp;u -= t * v;tmp = u;u = v;v = tmp;}u %= m;if (u < 0) u += m;return u;}}