結果
問題 | No.2877 Gunegune Hyperion |
ユーザー |
|
提出日時 | 2024-09-06 23:04:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,981 ms / 6,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 4,048 ms |
コンパイル使用メモリ | 244,980 KB |
最終ジャッジ日時 | 2025-02-24 04:52:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/modint>#include<atcoder/convolution>using namespace atcoder;using mint=modint998244353;using namespace std;using ll=long long;using poly=vector<mint>;void add(poly &A,poly B){if(A.size()<B.size())A.resize(B.size());for(int i=0;i<B.size();i++)A[i]+=B[i];return;}vector<vector<poly>> mul(vector<vector<poly>> &A,vector<vector<poly>> B){ll N=A.size();vector<vector<poly>> R(N,vector<poly>(N,{0}));for(int i=0;i<N;i++){for(int j=0;j<N;j++){for(int k=0;k<N;k++){add(R[i][j],convolution(A[i][k],B[k][j]));}}}return R;}int main() {ll N,H;cin>>N>>H;mint iv2=mint(2).inv();mint iv3=mint(3).inv();mint iv5=mint(5).inv();vector<vector<poly>> A={{{iv2},{iv3},{0}},{{0,iv2},{0,iv3},{0,iv3*2}},{{0},{0,iv3},{0,iv3}}};vector<vector<poly>> E={{{1},{0},{0}},{{0},{1},{0}},{{0},{0},{1}}};N--;while(N>0){if(N%2)E=mul(E,A);A=mul(A,A);N/=2;}poly AN={0};vector<poly> T={{iv5*2},{0,iv5*2},{0,iv5}};for(int i=0;i<3;i++){for(int j=0;j<3;j++){add(AN,convolution(T[j],E[i][j]));}}mint an=0;for(int h=H;h<ll(AN.size());h++)an+=AN[h];cout<<an.val()<<endl;}