結果
問題 | No.2367 Painting Gascket |
ユーザー |
|
提出日時 | 2021-06-21 18:21:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 2,026 bytes |
コンパイル時間 | 1,493 ms |
コンパイル使用メモリ | 168,352 KB |
実行使用メモリ | 8,936 KB |
最終ジャッジ日時 | 2024-07-07 06:20:16 |
合計ジャッジ時間 | 2,850 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll m = 1e9 + 7; ll mul(ll a, ll b = 1, ll c = 1, ll d = 1) { ll kj = a * b; kj %= m; kj *= c; kj %= m; kj *= d; kj %= m; return kj; } ll mpow(ll x, ll n) { ll ret = 1; while (n) { if (n % 2) { ret *= x; ret %= m; } x = (x * x) % m; n /= 2; } return ret; } int main() { int K; ll N; cin >> K >> N; if (N == 1) { cout << (K == 0 ? 1 : 0) << endl; return 0; } if (N == 2) { cout << 2 << endl; return 0; } ll dp[100100][7]; dp[0][0] = N; for (int i = 1; i <= 3; i++) { dp[0][i] = N - 1; } for (int i = 4; i < 6; i++) { dp[0][i] = N - 2; } dp[0][6] = N - 3; for (int i = 1; i <= K; i++) { dp[i][0] = mul(N, mpow(dp[i - 1][1], 3)); dp[i][1] = mul(N - 1, mpow(dp[i - 1][4], 2), dp[i - 1][1]); dp[i][1] += mul(mpow(dp[i - 1][2], 2), dp[i - 1][1]); if (dp[i][1] >= m) { dp[i][1] -= m; } dp[i][2] = mul(N - 1, dp[i - 1][5], mpow(dp[i - 1][4], 2)); dp[i][2] += mul(dp[i - 1][3], mpow(dp[i - 1][2], 2)); if (dp[i][2] >= m) { dp[i][2] -= m; } dp[i][3] = mul(N - 1, mpow(dp[i - 1][5], 3)); dp[i][3] += mpow(dp[i - 1][3], 3); if (dp[i][3] >= m) { dp[i][3] -= m; } dp[i][4] = mul(N - 2, dp[i - 1][6], mpow(dp[i - 1][4], 2)); dp[i][4] += mul(2, dp[i - 1][5], dp[i - 1][4], dp[i - 1][2]); if (dp[i][4] >= m) { dp[i][4] -= m; } dp[i][5] = mul(N - 2, dp[i - 1][5], mpow(dp[i - 1][6], 2)); dp[i][5] += mpow(dp[i - 1][5], 3); dp[i][5] += mul(mpow(dp[i - 1][5], 2), dp[i - 1][3]); dp[i][5] %= m; dp[i][6] = mul(N - 3, mpow(dp[i - 1][6], 3)); dp[i][6] += mul(3, dp[i - 1][6], mpow(dp[i - 1][5], 2)); } cout << dp[K][0] << endl; }