結果

問題 No.2857 Div Array
ユーザー nononnonon
提出日時 2024-08-25 14:22:10
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 5,753 bytes
コンパイル時間 2,619 ms
コンパイル使用メモリ 226,532 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-25 14:22:14
合計ジャッジ時間 3,809 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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;
}
0