結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:22:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 5,753 bytes |
コンパイル時間 | 2,226 ms |
コンパイル使用メモリ | 216,320 KB |
最終ジャッジ日時 | 2025-02-24 01:09:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/modint>using namespace std;template<typename mint>struct matrix{public:int row,col;matrix(int row, int col){this->row=row;this->col=col;this->A.resize(row);for(int i=0;i<row;i++)this->A[i].resize(col);}matrix(vector<vector<matrix>> M){int n=M.size(),m=M[0].size();int r=M[0][0].row,c=M[0][0].col;row=n*r,col=m*c;A.resize(row);for(int i=0;i<row;i++){A[i].resize(col);for(int j=0;j<col;j++){A[i][j]=M[i/r][j/c][i%r][j%c];}}}vector<mint>&operator[](int p){return this->A[p];}const vector<mint>&operator[](int p)const{return this->A[p];}matrix& operator+=(const matrix& B){assert(B.row==row);assert(B.col==col);B.col=1;for(int i=0;i<row;i++)for(int j=0;j<col;j++){this->A[i][j]+=B[i][j];}return *this;}matrix& operator-=(const matrix& B){assert(B.row==row);assert(B.col==col);for(int i=0;i<this->row;i++)for(int j=0;j<this->col;j++){this->A[i][j]-=B[i][j];}return *this;}matrix& operator*=(const matrix& B){assert(row==col);assert(B.row==row);assert(B.col==col);matrix res(row,row);for(int i=0;i<row;i++)for(int k=0;k<row;k++)for(int j=0;j<row;j++){res[i][j]+=this->A[i][k]*B[k][j];}return *this=res;}matrix operator*(const matrix& B)const{assert(B.row==col);matrix res(row,B.col);for(int i=0;i<row;i++)for(int k=0;k<col;k++)for(int j=0;j<B.col;j++){res[i][j]+=this->A[i][k]*B[k][j];}return res;}matrix& operator*=(const mint& r){for(int i=0;i<row;i++)for(int j=0;j<col;j++){this->A[i][j]*=r;}return *this;}matrix& operator/=(const mint& r){mint inv=mint(r).inv();(*this)*=inv;return *this;}matrix operator+(const matrix& B)const{return matrix(*this)+=B;}matrix operator-(const matrix &B)const{return matrix(*this)-=B;}matrix operator*(const mint& r)const{return matrix(*this)*=r;}matrix operator/(const mint& r)const{return matrix(*this)/=r;}bool operator==(const matrix& B)const{if(row!=B.row||col!=B.col)return 0;for(int i=0;i<row;i++)for(int j=0;j<col;j++)if(A[i][j]!=B[i][j])return 0;return 1;}bool operator!=(const matrix& B)const{if(row!=B.row||col!=B.col)return 1;for(int i=0;i<row;i++)for(int j=0;j<col;j++)if(A[i][j]!=B[i][j])return 1;return 0;}static constexpr matrix I(int n){matrix res(n,n);for(int i=0;i<n;i++)res[i][i]=mint::raw(1);return res;}static constexpr matrix O(int n, int m){return matrix(n,m);}matrix pow(long long k)const{assert(row==col);matrix B=*this;matrix res=I(row);while(k){if(k&1)res*=B;B*=B;k>>=1;}return res;}mint det()const{assert(row==col);int cnt=0;matrix B=*this;for(int i=0;i<row;i++){for(int j=i;j<row;j++)if(B[j][i]!=0){swap(B[i],B[j]);cnt+=j!=i;break;}for(int j=i+1;j<row;j++){if(B[i][i]==0)continue;mint inv=B[i][i].inv();inv*=B[j][i];for(int k=i+1;k<row;k++)B[j][k]-=B[i][k]*inv;}}mint res=1;for(int i=0;i<row;i++)res*=B[i][i];if(cnt&1)res*=-1;return res;}matrix inv()const{assert(row==col);assert(this->det()!=0);matrix B=*this;matrix invB=I(row);for(int i=0;i<row;i++){if(B[i][i]==0){for(int j=i+1;j<row;j++)if(B[j][i]!=0){swap(B[i],B[j]);swap(invB[i],invB[j]);break;}}mint cef=B[i][i].inv();for(int j=0;j<row;j++){B[i][j]*=cef;invB[i][j]*=cef;}for(int j=0;j<row;j++)if(i!=j){cef=B[j][i];for(int k=0;k<row;k++){B[j][k]-=B[i][k]*cef;invB[j][k]-=invB[i][k]*cef;}}}return invB;}matrix T()const{matrix res(col,row);for(int i=0;i<row;i++)for(int j=0;j<col;j++)res[j][i]=A[i][j];return res;}private:vector<vector<mint>>A;};using mint=atcoder::modint998244353;using mat=matrix<mint>;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,M,K;cin>>N>>M>>K;map<int,int>cnt;for(int i=1;i<=M;i++)cnt[M/i]++;int S=cnt.size();vector<int>num(S);int idx=0;for(auto[k,v]:cnt)num[idx++]=k;mat A(S,S);for(int i=0;i<S;i++)for(int j=0;j<S;j++)if(abs(num[i]-num[j])<=K){A[i][j]=cnt[num[j]];}// for(int i=0;i<S;i++)for(int j=0;j<S;j++)cout<<A[i][j].val()<<" \n"[j+1==S];A=A.pow(N-1);mint ans=0;for(int i=0;i<S;i++)for(int j=0;j<S;j++)ans+=cnt[num[i]]*A[i][j];cout<<ans.val()<<endl;}