結果
問題 | No.2877 Gunegune Hyperion |
ユーザー |
![]() |
提出日時 | 2024-09-06 22:20:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 978 ms / 6,000 ms |
コード長 | 2,891 bytes |
コンパイル時間 | 7,100 ms |
コンパイル使用メモリ | 290,688 KB |
実行使用メモリ | 26,748 KB |
最終ジャッジ日時 | 2024-09-06 22:21:50 |
合計ジャッジ時間 | 25,254 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
// g++-13 1.cpp -std=c++17 -O2 -I .#include <bits/stdc++.h>using namespace std;#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/tag_and_trait.hpp>using namespace __gnu_pbds;#include <atcoder/all>using namespace atcoder;using ll = long long;using ld = long double;using vi = vector<int>;using vvi = vector<vi>;using vll = vector<ll>;using vvll = vector<vll>;using vld = vector<ld>;using vvld = vector<vld>;using vst = vector<string>;using vvst = vector<vst>;#define fi first#define se second#define pb push_back#define eb emplace_back#define pq_big(T) priority_queue<T,vector<T>,less<T>>#define pq_small(T) priority_queue<T,vector<T>,greater<T>>#define all(a) a.begin(),a.end()#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())using mint = modint998244353;using fps = vector<mint>;random_device seed;mt19937_64 randint(seed());ll grr(ll mi, ll ma) { // [mi, ma)return mi + randint() % (ma - mi);}vector<vector<fps>> mul(vector<vector<fps>> &m1,vector<vector<fps>> &m2){// cout<<"call mul"<<endl;int x=m1.size();vector<vector<fps>> res(x,vector<fps>(x,{0}));rep(i,0,x){rep(j,0,x){rep(k,0,x){// [i][k] * [k][j]fps f=convolution(m1[i][k],m2[k][j]);int s=f.size();rep(l,0,s){if(l<res[i][j].size()){res[i][j][l]+=f[l];}else{res[i][j].emplace_back(f[l]);}}}}}return res;}vector<vector<fps>> pw(vector<vector<fps>> &mat,int n){// cout<<"call pw "<<n<<endl;int x=mat.size();if(n==0){vector<vector<fps>> res(x,vector<fps>(x,{0}));rep(i,0,x){res[i][i]={1};}return res;}if(n==1){return mat;}vector<vector<fps>> p=pw(mat,n/2),q=pw(mat,n%2);vector<vector<fps>> res=mul(p,p);res=mul(res,q);return res;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,h;cin>>n>>h;vector<vector<fps>> init(3,vector<fps>(3,{0}));mint inv2=1,inv3=1,inv5=1;inv2/=2,inv3/=3,inv5/=5;init[0][0]={inv2};init[0][1]={inv3};init[1][0]={0,inv2};init[1][1]={0,inv3};init[1][2]={0,inv3};init[2][1]={0,2*inv3};init[2][2]={0,inv3};vector<vector<fps>> mt=pw(init,n-1);vector<fps> f={{inv5,0},{0,inv5},{0,inv5}};// cout<<"mt ok"<<endl;mint ans=0;rep(i,0,3){rep(j,0,3){fps c=convolution(mt[i][j],f[j]);// cout<<i<<" # "<<j<<endl;// for(mint val:c){// cout<<(30*val).val()<<" ";// }// cout<<endl;rep(k,h,c.size()){ans+=c[k];if(i!=2)ans+=c[k];}}}cout<<ans.val()<<endl;}