結果
問題 | No.1513 simple 門松列 problem |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-05-21 22:08:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 564 ms / 3,000 ms |
コード長 | 1,916 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 209,524 KB |
最終ジャッジ日時 | 2024-04-18 15:37:34 |
合計ジャッジ時間 | 4,832 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
52,928 KB |
testcase_01 | AC | 39 ms
53,120 KB |
testcase_02 | AC | 564 ms
209,524 KB |
testcase_03 | AC | 51 ms
64,016 KB |
testcase_04 | AC | 41 ms
53,752 KB |
testcase_05 | AC | 54 ms
66,168 KB |
testcase_06 | AC | 69 ms
73,820 KB |
testcase_07 | AC | 45 ms
59,864 KB |
testcase_08 | AC | 88 ms
76,768 KB |
testcase_09 | AC | 38 ms
52,816 KB |
testcase_10 | AC | 39 ms
53,128 KB |
testcase_11 | AC | 39 ms
54,252 KB |
testcase_12 | AC | 43 ms
53,492 KB |
testcase_13 | AC | 38 ms
52,704 KB |
testcase_14 | AC | 558 ms
206,836 KB |
testcase_15 | AC | 557 ms
207,304 KB |
testcase_16 | AC | 553 ms
208,680 KB |
testcase_17 | AC | 386 ms
159,612 KB |
testcase_18 | AC | 180 ms
104,096 KB |
testcase_19 | AC | 91 ms
78,604 KB |
testcase_20 | AC | 146 ms
94,088 KB |
ソースコード
""" 大小が交互にやってくる 1つ前を持っていればよい 大小 最初大の場合を解く 総和は、通り数に適当にかけてあげればよいが 今までの総和を ?倍し、通り数 * 自分を加える 全部違ってか… 2つ前の値も持たなくてはいけない dp[i][j][k] = i番目まで見て、直前の値がjで、2つ前の値がkの時の通り数 3乗 j < k > x のとき、 dp[i][j][k] = sum(dp[i-1][k][x]) (ただし、x < k && x != j) kを小さい方から回し、jを小さい方からkまで回す j > k < xのとき、 kを大きいほうから回し、jを大きいほうからkまで回す sumはもとめておけばおk """ import sys from sys import stdin mod = 998244353 N,K = map(int,stdin.readline().split()) ans1 = 0 ans2 = 0 #大から始まる場合 dpA = [[[0] * K for j in range(K)] for i in range(N)] dpB = [[[0] * K for j in range(K)] for i in range(N)] for fi in range(K): for sc in range(K): if fi != sc: dpA[1][sc][fi] = 1 dpB[1][sc][fi] = sc + fi for i in range(2,N): nsuma = 0 nsumb = 0 for k in range(K): nsuma = (sum(dpA[i-1][k][:k])) % mod nsumb = (sum(dpB[i-1][k][:k])) % mod for j in range(k): dpA[i][j][k] = (nsuma - dpA[i-1][k][j]) % mod dpB[i][j][k] = (nsumb - dpB[i-1][k][j] + dpA[i][j][k] * j) % mod nsuma = 0 nsumb = 0 for k in range(K-1,-1,-1): nsuma = ( sum(dpA[i-1][k][k+1:])) % mod nsumb = ( sum(dpB[i-1][k][k+1:])) % mod for j in range(K-1,k,-1): dpA[i][j][k] = (nsuma - dpA[i-1][k][j]) % mod dpB[i][j][k] = (nsumb - dpB[i-1][k][j] + dpA[i][j][k] * j) % mod for j in range(K): for k in range(K): ans1 += dpA[N-1][j][k] ans2 += dpB[N-1][j][k] #print (dpA) print (ans1 % mod, ans2 % mod)