結果
問題 | No.2367 Painting Gascket |
ユーザー |
![]() |
提出日時 | 2023-07-17 04:50:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 2,024 bytes |
コンパイル時間 | 1,638 ms |
コンパイル使用メモリ | 169,008 KB |
実行使用メモリ | 16,752 KB |
最終ジャッジ日時 | 2024-09-17 21:20:48 |
合計ジャッジ時間 | 2,925 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = long long;const int N = 1e5 + 10, P = 1e9 + 7;int k, n;int qpow(int b, int k) {int ret = 1;while(k > 0) {if(k & 1) ret = (i64)ret * b % P;b = (i64)b * b % P;k >>= 1;}return ret;}i64 ch(i64 x) {return max(x, 0ll);}int sav[N][7], vis[N][7];int solve(int k, int type) {if(k == 0) {if(type == 0) return n;else if(type == 1 || type == 3 || type == 6) return ch(n - 1);else if(type == 2 || type == 5) return ch(n - 2);else if(type == 4) return ch(n - 3);}if(!vis[k][type]) {vis[k][type] = true;if(type == 0) sav[k][type] = (i64)n * qpow(solve(k - 1, 1), 3) % P;else if(type == 1) sav[k][type] = solve(k - 1, 1) * (qpow(solve(k - 1, 3), 2) + ch(n - 1ll) * qpow(solve(k - 1, 2), 2) % P) % P;else if(type == 2) sav[k][type] = ((i64)solve(k - 1, 5) * solve(k - 1, 2) % P * solve(k - 1, 3) * 2 + ch(n - 2ll) * solve(k - 1, 4) % P * qpow(solve(k - 1, 2), 2)) % P;else if(type == 3) sav[k][type] = ((i64)solve(k - 1, 6) * qpow(solve(k - 1, 3), 2) + ch(n - 1ll) * solve(k - 1, 5) % P * qpow(solve(k - 1, 2),2)) % P;else if(type == 4) sav[k][type] = (3ll * solve(k - 1, 4) % P * qpow(solve(k - 1, 5), 2) + ch(n - 3ll) * qpow(solve(k - 1, 4), 3)) % P;else if(type == 5) sav[k][type] = (solve(k - 1, 6) * (i64)qpow(solve(k - 1, 5), 2) + qpow(solve(k - 1, 5), 3) + ch(n - 2ll) * solve(k - 1, 5)% P * qpow(solve(k - 1, 4), 2)) % P;else if(type == 6) sav[k][type] = (qpow(solve(k - 1, 6), 3) + ch(n - 1ll) * qpow(solve(k - 1, 5), 3)) % P;}return sav[k][type];}/*0: uncolored1: 1 side colored2: 2 side colored with different colors3: 2 side colored with the same color4: 3 side colored with 3 colors5: 3 side colored with 2 colors6: 3 side colored with 1 color*/int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> k >> n;cout << solve(k, 0);}