結果

問題 No.541 3 x N グリッド上のサイクルの個数
コンテスト
ユーザー sadragonball
提出日時 2026-06-23 18:07:34
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,397 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,317 ms
コンパイル使用メモリ 165,612 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-06-23 18:07:49
合計ジャッジ時間 8,982 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20 RE * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <type_traits>

template<unsigned Mod>
class ModInt {
  unsigned v_;
  static unsigned norm(long long x) {
    x %= Mod;
    if (x < 0) x += Mod;
    return (unsigned)x;
  }

public:
  ModInt(long long v = 0) : v_(norm(v)) {}

  unsigned val() const { return v_; }

  ModInt& operator+=(const ModInt& o) {
    v_ += o.v_;
    if (v_ >= Mod) v_ -= Mod;
    return *this;
  }

  friend ModInt operator+(ModInt a, const ModInt& b) {
    return a += b;
  }
};

using mint = ModInt<1000000007>;

static const int S = 8; // 3-bit states

std::vector<int> nxt[S];

void build_transitions() {
  for (int k = 0; k < S; ++k) {
    for (int j = 0; j < S; ++j) {
      if ((k & ~j) == 0) {
        nxt[k].push_back(j);
      }
    }
  }
}

mint dp[55][S];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N;
  std::cin >> N;

  build_transitions();

  // 初始化：第一列所有状态都可能出现（无额外限制时）
  for (int s = 0; s < S; ++s) {
    dp[1][s] = 1;
  }

  // DP
  for (int i = 2; i <= N; ++i) {
    for (int k = 0; k < S; ++k) {
      if (dp[i - 1][k].val() == 0) continue;
      for (int j : nxt[k]) {
        dp[i][j] += dp[i - 1][k];
      }
    }
  }

  // 汇总所有状态
  mint res = 0;
  for (int s = 0; s < S; ++s) {
    res += dp[N][s];
  }

  std::cout << res.val() << "\n";
  return 0;
}
0