結果

問題 No.3182 recurrence relation’s intersection sum
コンテスト
ユーザー alcea
提出日時 2025-06-13 22:28:18
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 547 ms / 2,000 ms
コード長 2,996 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,477 ms
コンパイル使用メモリ 206,208 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-13 22:28:30
合計ジャッジ時間 11,770 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
template<long long mod>
struct modint{
  long long v;
  modint(long long x=0):v((x%=mod)<0?x+mod:x){}
  constexpr long long val()noexcept{return v;}
  constexpr modint& operator=(const modint o){v=o.v;return *this;}
  constexpr modint& operator+=(const modint o)noexcept{if((v+=o.v)>=mod)v-=mod;return *this;}
  constexpr modint& operator-=(const modint o)noexcept{if((v-=o.v)<0)v+=mod;return *this;}
  constexpr modint& operator*=(const modint o)noexcept{v=v*o.v%mod;return *this;}
  constexpr modint& operator/=(modint o)noexcept{return *this*=o.inv();}
  constexpr modint pow(long long n)noexcept{
    modint ret=1,base=*this;
    while(n>0){if(n&1)ret*=base;base*=base;n/=2;}
    return ret;
  }
  constexpr modint inv()noexcept{return pow(mod-2);}
  constexpr modint operator+(const modint o)noexcept{return modint(*this)+=o;}
  constexpr modint operator+()noexcept{return *this;}
  constexpr modint operator-(const modint o)noexcept{return modint(*this)-=o;}
  constexpr modint operator-()noexcept{return modint()-*this;}
  constexpr modint operator*(const modint o)noexcept{return modint(*this)*=o;}
  constexpr modint operator/(const modint o)noexcept{return modint(*this)/=o;}
  constexpr modint& operator++()noexcept{return *this+=1;}
  constexpr modint operator++(int)noexcept{return (*this+=1)-1;}
  constexpr modint& operator--()noexcept{return *this-=1;}
  constexpr modint operator--(int)noexcept{return (*this-=1)+1;}
  constexpr bool operator==(const modint o)noexcept{return v==o.v;}
  constexpr bool operator!=(const modint o)noexcept{return v!=o.v;}
  friend ostream& operator<<(ostream& os,const modint o)noexcept{os<<o.v;return os;}
};
using mint=modint<998244353>;
int main(){
  long long k,l,r;
  cin>>k>>l>>r;
  int m=k+4;
  vector<vector<mint>> mat(m,vector<mint>(m,0));
  mat[0][0]=k+1;
  mat[0][1]=-k;
  mat[0][2]=1;
  mat[0][3]=1;
  mat[1][0]=1;
  mat[2][2]=k;
  mint fact[k+1];
  fact[0]=1;
  for(int i=1;i<=k;i++) fact[i]=fact[i-1]*i;
  for(int i=0;i<=k;i++) for(int j=0;j<=k;j++){
    if(i<j) continue;
    mat[k-i+3][k-j+3]=fact[i]/fact[j]/fact[i-j];
  }
  auto mul=[&](vector<vector<mint>> matrix1,vector<vector<mint>> matrix2){
    vector<vector<mint>> ret(m,vector<mint>(m,0));
    for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int l=0;l<m;l++) ret[i][j]+=matrix1[i][l]*matrix2[l][j];
    return ret;
  };
  auto mat_l=mat;
  vector<vector<mint>> e(m,vector<mint>(m,0));
  for(int i=0;i<m;i++) e[i][i]=1;
  auto e_l=e;
  while(l>0){
    if(l&1) e_l=mul(mat_l,e_l);
    mat_l=mul(mat_l,mat_l);
    l>>=1;
  }
  auto mat_r=mat;
  auto e_r=e;
  while(r>0){
    if(r&1) e_r=mul(mat_r,e_r);
    mat_r=mul(mat_r,mat_r);
    r>>=1;
  }
  mint sl=0,sr=0;
  vector<mint> v0(m,0);
  v0[0]=1;
  v0[2]=1;
  v0[m-1]=1;
  for(int i=0;i<m;i++){
    sl+=e_l[1][i]*v0[i];
    sr+=e_r[0][i]*v0[i];
  }
  //for(int i=0;i<m;i++) for(int j=0;j<m;j++) cerr<<mat[i][j]<<" \n"[j==m-1];
  cout<<(sr-sl)<<endl;
  //cerr<<sl<<" "<<sr<<endl;
}
0