結果
問題 | No.2874 Gunegune Tree |
ユーザー | tottoripaper |
提出日時 | 2024-09-08 23:42:55 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 2,384 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 217,536 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-08 23:43:00 |
合計ジャッジ時間 | 5,057 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) using ll = std::int64_t; using P = std::tuple<int, int>; std::tuple<ll, ll, ll> extgcd(ll a, ll b){ ll s1 = 1, t1 = 0, s2 = 0, t2 = 1; while(b != 0){ std::tie(s1, t1, s2, t2) = std::make_tuple(s2, t2, s1 - (a / b) * s2, t1 - (a / b) * t2); std::tie(a, b) = std::make_tuple(b, a % b); } return std::make_tuple(s1, t1, a); } ll inv(ll a, ll n){ ll inv_a; std::tie(inv_a, std::ignore, std::ignore) = extgcd(a, n); inv_a %= n; if(inv_a < 0){inv_a += n;} return inv_a; } ll pow(ll a, ll n, ll m){ ll p = 1; while(n > 0){ if(n & 1){ p = p * a % m; } a = a * a % m; n /= 2; } return p; } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int N; std::cin >> N; constexpr ll MOD = 998'244'353; std::vector dp(2, std::vector<ll>(5, 0)); std::vector p(2, std::vector<ll>(5, 0)); ll inv_5 = inv(5, MOD); for(int i=0;i<5;i++){ if(1 <= i && i <= 3){ dp[1][i] = inv_5; } p[1][i] = inv_5; } auto trans = [](int j, int k){ if(j == k){ return true; } if(j == 0){ return k == 1; } if(j == 4){ return k == 3; } return std::abs(j - k) == 1; }; for(int i=0;i<N-1;i++){ std::swap(dp[0], dp[1]); std::fill(std::begin(dp[1]), std::end(dp[1]), 0); std::swap(p[0], p[1]); std::fill(std::begin(p[1]), std::end(p[1]), 0); for(int j=0;j<5;j++){ int n = 0; for(int k=0;k<5;k++){ if(trans(j, k)){n += 1;} } ll inv_n = inv(n, MOD); for(int k=0;k<5;k++){ if(!trans(j, k)){continue;} ll q = p[0][j] * inv_n % MOD; dp[1][k] += dp[0][j] * inv_n % MOD; if(dp[1][k] >= MOD){dp[1][k] -= MOD;} dp[1][k] += (1 <= k && k <= 3 ? q : 0); if(dp[1][k] >= MOD){dp[1][k] -= MOD;} p[1][k] += q; if(p[1][k] >= MOD){p[1][k] -= MOD;} } } } ll res = std::accumulate(std::begin(dp[1]), std::end(dp[1]), 0ll) % MOD; std::cout << res << std::endl; }