結果
問題 | No.2367 Painting Gascket |
ユーザー |
![]() |
提出日時 | 2023-06-30 22:46:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,930 bytes |
コンパイル時間 | 1,381 ms |
コンパイル使用メモリ | 170,904 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-07 10:38:23 |
合計ジャッジ時間 | 5,082 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 2 |
other | AC * 9 RE * 25 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 1000000007;int main(){int K;long long N;cin >> K >> N;assert(K <= 2);vector<long long> dp000(K + 1, 0);vector<long long> dp001(K + 1, 0);vector<long long> dp011(K + 1, 0);vector<long long> dp012(K + 1, 0);vector<long long> dp111(K + 1, 0);vector<long long> dp112(K + 1, 0);vector<long long> dp123(K + 1, 0);dp000[0] = N;dp001[0] = N - 1;dp011[0] = N - 1;dp012[0] = max(N - 2, (long long) 0);dp111[0] = N - 1;dp112[0] = max(N - 2, (long long) 0);dp123[0] = max(N - 3, (long long) 0);for (int i = 0; i < K; i++){dp000[i + 1] = N * dp001[i] % MOD * dp001[i] % MOD * dp001[i] % MOD;dp001[i + 1] += (N - 1) * dp001[i] % MOD * dp012[i] % MOD * dp012[i] % MOD;dp001[i + 1] += dp001[i] * dp011[i] % MOD * dp011[i] % MOD;dp001[i + 1] %= MOD;dp011[i + 1] += (N - 1) * dp012[i] % MOD * dp012[i] % MOD * dp112[i] % MOD;dp011[i + 1] += dp011[i] * dp011[i] % MOD * dp111[i] % MOD;dp011[i + 1] %= MOD;if (N >= 2){dp012[i + 1] += (N - 2) * dp012[i] % MOD * dp012[i] % MOD * dp123[i] % MOD;dp012[i + 1] += 2 * dp011[i] % MOD * dp012[i] % MOD * dp112[i] % MOD;dp012[i + 1] %= MOD;}dp111[i + 1] += (N - 1) * dp112[i] % MOD * dp112[i] % MOD * dp112[i] % MOD;dp111[i + 1] += dp111[i] * dp111[i] % MOD * dp111[i] % MOD;dp111[i + 1] %= MOD;if (N >= 2){dp112[i + 1] += (N - 2) * dp112[i] % MOD * dp123[i] % MOD * dp123[i] % MOD;dp112[i + 1] += dp112[i] * dp112[i] % MOD * dp111[i] % MOD;dp112[i + 1] += dp112[i] * dp112[i] % MOD * dp112[i] % MOD;dp112[i + 1] %= MOD;}if (N >= 3){dp123[i + 1] += (N - 3) * dp123[i] % MOD * dp123[i] % MOD * dp123[i] % MOD;dp123[i + 1] += 3 * dp112[i] % MOD * dp123[i] % MOD * dp123[i] % MOD;dp123[i + 1] %= MOD;}}cout << dp000[K] << endl;}