結果
問題 | No.1887 K Consecutive Ks (Easy) |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2022-03-25 22:57:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 1,761 bytes |
コンパイル時間 | 420 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 147,072 KB |
最終ジャッジ日時 | 2024-04-22 07:47:24 |
合計ジャッジ時間 | 5,614 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
53,376 KB |
testcase_01 | AC | 38 ms
52,884 KB |
testcase_02 | AC | 589 ms
147,072 KB |
testcase_03 | AC | 38 ms
53,564 KB |
testcase_04 | AC | 38 ms
52,068 KB |
testcase_05 | AC | 38 ms
53,160 KB |
testcase_06 | AC | 39 ms
52,600 KB |
testcase_07 | AC | 52 ms
63,316 KB |
testcase_08 | AC | 62 ms
68,568 KB |
testcase_09 | AC | 50 ms
63,876 KB |
testcase_10 | AC | 62 ms
69,360 KB |
testcase_11 | AC | 166 ms
90,392 KB |
testcase_12 | AC | 105 ms
81,380 KB |
testcase_13 | AC | 564 ms
144,188 KB |
testcase_14 | AC | 580 ms
146,356 KB |
testcase_15 | AC | 589 ms
146,280 KB |
testcase_16 | AC | 434 ms
124,820 KB |
testcase_17 | AC | 384 ms
124,920 KB |
testcase_18 | AC | 589 ms
147,032 KB |
ソースコード
""" 1887 まぁ、ない場合を計算すればヨシ dp[i][v] = i番目まで見て、i番目に置いたのがvの場合の数…? 同じ数字はまとめておくことにする。 推移を考える。 まず、区間の長さを決めると、その数字は使用不可になる。 また、直前の数字は使用不可となる。 貰うdpで考えるか~ 貰う時、lastindexを指定したとする。 直前の区間長に等しい色の場合に関しては、最初から全部除いておいていい。 自分の選ぶ色に関しては、 色cを選んだとき、 直前同じ色の時だけ、さらに除く。 ただし、あらかじめ除かれている場合はもう気にしなくてよい。 dp[i][c] に推移できないのは dp[i-c以下][?] か dp[?][c] である。 indsumは大きいほうから累積和しておく。 dp[?][c] の方は… 2 3 3*3 = 9通り 23 32 11 33 → 11 がまずいのか """ import sys from sys import stdin def ss(x1,y1,x2,y2): if x1 > x2 or y1 > y2: return 0 x1 = max(x1,0) ret = dp[x2][y2] if x1-1 >= 0: ret -= dp[x1-1][y2] if y1-1 >= 0: ret -= dp[x2][y1-1] if x1-1 >= 0 and y1-1 >= 0: ret += dp[x1-1][y1-1] return ret N,M = map(int,stdin.readline().split()) dp = [[0] * (M+1) for i in range(N+1)] dp[0] = [1] * (M+1) mod = 998244353 for i in range(1,N+1): for c in range(1,M+1): dp[i][c] = ( ss(i-c+1,0,i-1,M) - ss(i-c+1,c,i-1,c) ) % mod for c in range(M): dp[i][c+1] += dp[i][c] dp[i][c+1] %= mod for c in range(M+1): dp[i][c] += dp[i-1][c] dp[i][c] %= mod #print (dp) ansrev = (ss(N,0,N,M) % mod) ans = pow(M,N,mod) - ansrev print (ans % mod)