結果
問題 | No.2367 Painting Gascket |
ユーザー |
![]() |
提出日時 | 2023-06-30 01:54:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,959 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 72,564 KB |
最終ジャッジ日時 | 2024-07-07 06:20:28 |
合計ジャッジ時間 | 3,130 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
# 難しい# 部分的なグラフを 6 種類程度考え, それは DP になるだろう.# dp1[i]# = (A) dp1[i-1] ** 3# + (B) (n-1) * dp2[i-1] ** 3# dp2[i]# = (A) dp2[i-1] ** 3# + (B) dp1[i-1] * dp2[i-1] ** 2# + (C) (n-2) * dp2[i-1] * dp3[i-1] ** 2# dp3[i]# = (A, B, C) 3 * dp2[i-1] ** 2 * dp3[i-1]# + (D) (n-3) * dp3[i-1] ** 3# dp4[i]# = (A) dp1[i-1] * dp4[i-1] ** 2# + (B) (n-1) * dp2[i-1] * dp5[i-1] ** 2# dp5[i]# = (A, B) 2 * dp2[i-1] * dp4[i-1] * dp5[i-1]# = (C) (n-2) * dp1[i-1] * dp5[i-1] ** 2# dp6[i]# = (A) dp4[i-1] ** 2 * dp6[i-1]# + (B) (n-1) * dp5[i-1] ** 2 * dp6[i-1]# 答えは dp6[k-1] ** 3 * n# 初期値# dp1[0] = n-1# dp2[0] = n-2# dp3[0] = n-3# dp4[0] = n-1# dp5[0] = n-2# dp6[0] = n-1mod = 10 ** 9 + 7k, n = map(int,input().split())if k == 0:print(n % mod)exit()dp1 = [0] * kdp2 = [0] * kdp3 = [0] * kdp4 = [0] * kdp5 = [0] * kdp6 = [0] * kdp1[0] = n-1dp2[0] = n-2dp3[0] = n-3dp4[0] = n-1dp5[0] = n-2dp6[0] = n-1for i in range(1, k):dp1[i] = dp1[i-1] * dp1[i-1] % mod * dp1[i-1] % mod\+ dp2[i-1] * dp2[i-1] % mod * dp2[i-1] % mod * (n-1) % moddp2[i] = dp2[i-1] * dp2[i-1] % mod * dp2[i-1] % mod\+ dp1[i-1] * dp2[i-1] % mod * dp2[i-1] % mod\+ dp2[i-1] * dp3[i-1] % mod * dp3[i-1] % mod * (n-2) % moddp3[i] = dp2[i-1] * dp2[i-1] % mod * dp3[i-1] % mod * 3 % mod\+ dp3[i-1] * dp3[i-1] % mod * dp3[i-1] % mod * (n-3) % moddp4[i] = dp1[i-1] * dp4[i-1] % mod * dp4[i-1] % mod\+ dp2[i-1] * dp5[i-1] % mod * dp5[i-1] % mod * (n-1) % moddp5[i] = dp2[i-1] * dp4[i-1] % mod * dp5[i-1] % mod * 2 % mod\+ dp3[i-1] * dp5[i-1] % mod * dp5[i-1] % mod * (n-2) % moddp6[i] = dp4[i-1] * dp4[i-1] % mod * dp6[i-1] % mod\+ dp5[i-1] * dp5[i-1] % mod * dp6[i-1] % mod * (n-1) % moddp1[i] %= moddp2[i] %= moddp3[i] %= moddp4[i] %= moddp5[i] %= moddp6[i] %= mod#print(dp6[0])print(dp6[k-1] * dp6[k-1] % mod * dp6[k-1] % mod * n % mod)