結果

問題 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;
}
0