結果
問題 |
No.3044 よくあるカエルさん
|
ユーザー |
![]() |
提出日時 | 2025-02-28 23:09:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,033 ms / 2,000 ms |
コード長 | 903 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 79,216 KB |
最終ジャッジ日時 | 2025-02-28 23:09:39 |
合計ジャッジ時間 | 9,018 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
N, T = map(int, input().split()) K, L = map(int, input().split()) N -= 1 if N == 0: exit(print(1)) MOD = 998244353 def inverse(n, d): return n * pow(d, -1, MOD) % MOD def matrix(a, b): ans = [[0]*len(b[0]) for _ in range(len(a))] for i in range(len(a)): for j in range(len(b[0])): ans[i][j] = sum(a[i][k]*b[k][j] for k in range(len(b)))%MOD return ans dp = [[[0]*T for _ in range(T)]] for i in range(1, T): dp[0][i-1][i] = 1 for i in range(1, K): dp[0][0][0] += inverse(1, 6) dp[0][0][0] %= MOD for i in range(K, L): dp[0][1][0] += inverse(1, 6) dp[0][1][0] %= MOD for i in range(L, 7): dp[0][T-1][0] += inverse(1, 6) dp[0][T-1][0] %= MOD for _ in range(29): dp.append(matrix(dp[-1], dp[-1])) ans = [[0] for _ in range(T)] ans[0][0] = 1 for i in range(30): if 1<<i & N: ans = matrix(dp[i], ans) print(ans[0][0])