結果

問題 No.2857 Div Array
ユーザー nonon
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

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