結果
問題 | No.3182 recurrence relation’s intersection sum |
ユーザー |
|
提出日時 | 2025-06-13 22:28:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 2,996 bytes |
コンパイル時間 | 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 |
ソースコード
#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; }