結果
問題 | No.2668 Trees on Graph Paper |
ユーザー |
![]() |
提出日時 | 2024-03-08 23:29:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,605 ms / 3,000 ms |
コード長 | 1,442 bytes |
コンパイル時間 | 663 ms |
コンパイル使用メモリ | 77,656 KB |
最終ジャッジ日時 | 2025-02-20 03:08:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <map> using namespace std; int main() { int N; cin >> N; int mod; cin>>mod; vector<long long> dp(3, 0); dp[2] = 1; vector<long long> score(3, 0); score[2] = 1; long long result = 1; for (int x = 1; x < 2 * N; ++x) { result *= x; result %= mod; } for (int i = 1; i < 2 * N - 1; ++i) { vector<long long> dp2(3, 0); vector<long long> score2(3, 0); for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { if (j == 2 && k == 0) { continue; } dp2[k] += dp[j]; dp2[k] %= mod; if (k <= j) { score2[k] += score[j]; } else if (k == 1 && j == 0) { score2[k] += score[j] * (i - 1); } else if (k == 2 && j == 1) { score2[k] += score[j] * i; } else { long long w = score[j] * i; w %= mod; w *= i - 1; w %= mod; score2[k] += w; } score2[k] %= mod; } } dp = dp2; score = score2; if (i % 2 == 0) { result *= score[0]; result %= mod; } } cout << result << endl; return 0; }