結果
問題 | No.2514 Twelvefold Way Returns |
ユーザー |
|
提出日時 | 2023-10-20 22:32:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 671 ms / 3,000 ms |
コード長 | 3,324 bytes |
コンパイル時間 | 6,487 ms |
コンパイル使用メモリ | 177,336 KB |
最終ジャッジ日時 | 2025-02-17 10:13:58 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>#include <atcoder/modint>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i=0;i<n;i+=1)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<"\n";}template<class T>ostream& operator<<(ostream& os, const vec<T>& A){os << "{";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ", ";}}os << "}" ;return os;}template<class T>ostream& operator<<(ostream& os, const deque<T>& A){os << "deque{[";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ", ";}}os << "]}" ;return os;}template<class T>ostream& operator<<(ostream& os, const pair<T,T>& A){os << "(";os << A.first ;os << ", ";os << A.second;os << ")";return os;}pair<mint,mint> omega_prod(pair<mint,mint> X,pair<mint,mint> Y){auto [a,b] = X;auto [c,d] = Y;return {(a*d+b*c-a*c),b*d-a*c};};pair<mint,mint> omega_pow(pair<mint,mint> X,int N){pair<mint,mint> res = {0,1};while (N){if ((N&1)){res = omega_prod(res,X);}X = omega_prod(X,X);N >>= 1;}return res;}ostream& operator<<(ostream& os, const mint a){os << a.val();return os;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin>>N>>M;vec<vec<pair<mint,mint>>> dp(2*M+1,vec<pair<mint,mint>>(2*M+1,{0,0}));pair<mint,mint> zero = {0,0};dp[M][M] = {0,1};mint i3 = mint(3).inv();for (int _=0;_<M;_++){vec<vec<pair<mint,mint>>> ndp(2*M+1,vec<pair<mint,mint>>(2*M+1,{0,0}));for (int i=0;i<=2*M;i++){for (int j=0;j<=2*M;j++){if (dp[i][j] == zero) continue;auto e = dp[i][j];ndp[i][j+1].first += e.first * i3;ndp[i][j+1].second += e.second * i3;e = omega_prod(e,{1,0});ndp[i-1][j-1].first += e.first * i3;ndp[i-1][j-1].second += e.second * i3;e = omega_prod(e,{1,0});ndp[i+1][j].first += e.first * i3;ndp[i+1][j].second += e.second * i3;}}swap(dp,ndp);}mint res = 0;for (int i=0;i<=2*M;i++){for (int j=0;j<=2*M;j++){auto e = omega_pow({i-M,j-M},N);auto f = omega_prod(dp[i][j],e);res += f.second;}}cout << res.val() << endl;}