結果
問題 | No.2874 Gunegune Tree |
ユーザー |
|
提出日時 | 2024-09-08 06:41:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 1,078 bytes |
コンパイル時間 | 4,058 ms |
コンパイル使用メモリ | 253,052 KB |
最終ジャッジ日時 | 2025-02-24 05:16:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using mint = atcoder::modint998244353;int main(){int n;cin >> n;vector<pair<int,int>> dir = {{1, 1}, {0, 1}, {-1, 1}, {1, 0}, {-1, 0}};auto check = [&](int i, int j){auto [dx1, dy1] = dir[i];auto [dx2, dy2] = dir[j];dx1 *= -1, dy1 *= -1;return dx1 * dx2 + dy1 * dy2 < 0;};vector<int> A(5);array<array<mint,5>,5> B;for(int i = 0; i < 5; i++){for(int j = 0; j < 5; j++){A[i] |= check(i, j) << j;}B[i].fill(mint(1) / __builtin_popcount(A[i]));}mint ans;array<mint, 5> dp;dp.fill(mint(1) / 5);ans += 3 * dp[0];for(int i = 1; i < n; i++){array<mint, 5> ndp;for(int j = 0; j < 5; j++){for(int k = 0; k < 5; k++){if(A[j] >> k & 1){ndp[k] += B[j][k] * dp[j];}}}swap(dp, ndp);ans += dp[0] + dp[1] + dp[2];}cout << ans.val() << '\n';}