結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0