結果

問題 No.1050 Zero (Maximum)
コンテスト
ユーザー xenon_motsu
提出日時 2020-05-08 21:49:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 6,640 bytes
コンパイル時間 3,040 ms
コンパイル使用メモリ 204,472 KB
最終ジャッジ日時 2025-01-10 08:34:30
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct modint{
    using i64=int_fast64_t;
    i64 a;
    static constexpr i64 MOD=1e9+7;
    constexpr modint():a(){}
    constexpr modint(i64 a_):a(a_%MOD){
        if(a<0) a+=MOD;
    }
    constexpr modint inv()const noexcept{
        i64 n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y;
        y.a=n;
        return y;
    }
    constexpr modint operator+()noexcept{
        return *this;
    }
    constexpr modint operator-()noexcept{
        modint tmp{};
        if(a) tmp.a=MOD-a;
        return tmp;
    }
    constexpr modint& operator++()noexcept{
        ++a;
        if(a==MOD) a=0;
        return *this;
    }
    constexpr modint& operator--()noexcept{
        if(a) --a;
        else a=MOD-1;
        return *this;
    }
    constexpr modint operator++(int)noexcept{
        modint tmp=*this;
        ++a;
        if(a==MOD) a=0;
        return tmp;
    }
    constexpr modint operator--(int)noexcept{
        modint tmp=*this;
        if(a) --a;
        else a=MOD-1;
        return tmp;
    }
    constexpr bool operator==(const modint& x)const noexcept{
        return a==x.a;
    }
    constexpr bool operator!=(const modint& x)const noexcept{
        return a!=x.a;
    }
    constexpr modint operator+(const modint& x)const noexcept{
        modint y;
        y.a=a+x.a;
        if(y.a>=MOD) y.a-=MOD;
        return y;
    }
    constexpr modint operator-(const modint& x)const noexcept{
        modint y;
        y.a=a-x.a;
        if(y.a<0) y.a+=MOD;
        return y;
    }
    constexpr modint operator*(const modint& x)const noexcept{
        modint y;
        y.a=(a*x.a)%MOD;
        return y;
    }
    constexpr modint operator/(const modint& x)const noexcept{
        modint y;
        y.a=(a*x.inv().a)%MOD;
        return y;
    }
    constexpr modint& operator+=(const modint& x)noexcept{
        a+=x.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    constexpr modint& operator-=(const modint& x)noexcept{
        a-=x.a;
        if(a<0) a+=MOD;
        return *this;
    }
    constexpr modint& operator*=(const modint& x)noexcept{
        (a*=x.a)%=MOD;
        return *this;
    }
    constexpr modint& operator/=(const modint& x)noexcept{
        (a*=x.inv().a)%=MOD;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x)noexcept{
    static int_fast64_t a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x)noexcept{
    out<<x.a;
    return out;
}
constexpr modint pwr(int_fast64_t a,int_fast64_t b)noexcept{
    modint _;
    int_fast64_t n=1,A=a;
    while(b){
        if(b&1) (n*=A)%=modint::MOD;
        (A*=A)%=modint::MOD;
        b>>=1;
    }
    _.a=n;
    return _;
}

template<class T> struct mat{
    int n,m;
    vector<vector<T>> v;
    T a;
    mat(int e=0){
        n=-1;
        if(e==0) m=0;
        else if(e==1) m=1;
        else m=-1;
    }
    mat(int n_,int m_,T e){
        n=n_;m=m_;
        v.clear();
        v.resize(n);
        fr(i,n){
            v[i].resize(m);
            if(i<m) v[i][i]=e;
        }
    }
    mat(vector<vector<T>>& v_){
        n=v_.size();
        m=v_[0].size();
        swap(v,v_);
    }
    bool operator==(const mat& x){
        if(n!=x.n||m!=x.m) return 0;
        fr(i,n) fr(j,m) if(v[i][j]!=x.v[i][j]) return 0;
        return 1;
    }
    mat& operator=(const mat& x){
        n=x.n;
        m=x.m;
        v=vector<vector<T>>(n);
        copy(x.v.begin(),x.v.end(),v.begin());
        return *this;
    }
    mat operator+(const mat& x){
        if(n==-1&&m==0) return x;
        if(x.n==-1&&x.m==0) return *this;
        if(n!=x.n||m!=x.m) return mat();
        vector<vector<T>> y(n,vector<T>(m));
        fr(i,n) fr(j,m) y[i][j]=v[i][j]+x.v[i][j];
        return mat(y);
    }
    mat operator-(const mat& x){
        if(n==-1&&m==0){
            vector<vector<T>> y(x.n,vector<T>(x.m));
            fr(i,x.n) fr(j,x.m) y[i][j]=T()-x.v[i][j];
            return mat(y);
        }
        if(x.n==-1&&x.m==0) return *this;
        if(n!=x.n||m!=x.m) return mat();
        vector<vector<T>> y(n,vector<T>(m));
        fr(i,n) fr(j,m) y[i][j]=v[i][j]-x.v[i][j];
        return mat(y);
    }
    mat operator*(const mat& x){
        if(n==-1&&m==1) return x;
        if(x.n==-1&&x.m==1) return *this;
        if(m!=x.n) return mat();
        vector<vector<T>> y(n,vector<T>(x.m));
        fr(i,n) fr(k,m) fr(j,x.m) y[i][j]+=v[i][k]*x.v[k][j];
        return mat(y);
    }
    mat& operator+=(const mat& x){
        if(n!=x.n||m!=x.m) return mat();
        fr(i,n) fr(j,m) v[i][j]+=x.v[i][j];
        return *this;
    }
    mat& operator-=(const mat& x){
        if(n!=x.n||m!=x.m) return mat();
        fr(i,n) fr(j,m) v[i][j]-=x.v[i][j];
        return *this;
    }
    mat& operator*=(const mat& x){
        *this=*this*x;
        return *this;
    }
    T& operator()(int i,int j){
        return v[i][j];
    }
    T det(){
        if(n==0){
            if(m==0) return T();
            if(m==1) return T(1);
        }
        if(n!=m) return T();
        mat y=*this;
        int c=1;
        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                if(v[j][i]!=T()){
                    if(i!=j){
                        swap(v[i],v[j]);
                        c*=-1;
                    }
                    break;
                }
                if(j==n-1) return T();
            }
            for(int j=i+1;j<n;++j){
                T ka=v[j][i]/v[i][i];
                for(int k=i;k<n;k++){
                    v[j][k]-=v[i][k]*ka;
                }
            }
        }
        T d=T(1);
        for(int i=0;i<n;i++) d*=v[i][i];
        d*=c;
        *this=y;
        return d;
    }
};

template<class T,class U>
T pw(T n,U m){
    if(m==0) return T(1);
    else if(m%2==0) return pw(n*n,m/2);
    else return n*pw(n,m-1);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int m,k;
    cin>>m>>k;
    mat<modint> mt(m,m,0),v(m,1,1);
    fr(l,m){
        fr(i,m){
            ++mt(l,(l+i)%m);
            ++mt(l,(l*i)%m);
        }
    }
    v=pw(mt,k)*v;
    cout<<v(0,0)<<'\n';
}
0