結果
問題 | No.2668 Trees on Graph Paper |
ユーザー |
|
提出日時 | 2023-12-28 03:41:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 544 ms / 3,000 ms |
コード長 | 1,485 bytes |
コンパイル時間 | 739 ms |
コンパイル使用メモリ | 71,424 KB |
最終ジャッジ日時 | 2025-02-18 14:48:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <array>#include <iostream>#include <atcoder/modint>int main() {using mint = atcoder::modint;int n, m;std::cin >> n >> m;mint::set_mod(m);mint ans = 1;std::array<std::array<mint, 2>, 2> pd{};pd[0][0] = { 1 };for (int x = 0; x < 2 * n - 3; ++x) {// pd: dp(x,*,*), dp: dp(x+1,*,*)std::array<std::array<mint, 2>, 2> dp{};for (int f : { 0, 1 }) {// T: tofu, R: red ball, W: white ball// g=0 (RTRT...RT){constexpr int g = 0;const mint val = pd[f][g];// Wdp[0][0] += val;// Rdp[1][1] += val;}// g=1 (RTRT...TR){constexpr int g = 1;const mint val = pd[f][g];// Wdp[0][1] += val;// TRmint weightR = f ? 1 : x; // if f=0 then vertex (x,_) has degree of 1dp[1][1] += val * weightR;// TWmint weightW = weightR * (x + 1); // vertex (x+1,_) has degree of 1dp[0][0] += val * weightW;}}dp.swap(pd);if (x % 2 == 0) {// level x/2+1ans *= pd[0][1] + pd[1][1];}}// level nfor (int x = 1; x <= 2 * n - 1; ++x) {ans *= x;}std::cout << ans.val() << std::endl;}