結果

問題 No.1050 Zero (Maximum)
ユーザー 沙耶花
提出日時 2020-05-08 21:40:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,297 bytes
コンパイル時間 2,627 ms
コンパイル使用メモリ 206,160 KB
最終ジャッジ日時 2025-01-10 08:23:04
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000
int beki(int a,int b){
    int x = 1;
    while(b!=0){
        if(b&1){
            x=mod(x*a);
        }
        a=mod(a*a);
        b>>=1;
    }
    return x;
}
struct matrix{
    vector<vector<long long>> value;
    
    matrix(int height,int width){
        value.resize(height,vector<long long>(width,0));
        if(height==width){
            for(int i=0;i<get_width();i++){
                value[i][i] = 1;
            }
        }
    }
    
    void resize(int height,int width){
        value.resize(height,vector<long long>(width,0));
        for(int i=0;i<get_width();i++){
            value[i][i] = 1;
        }
    }
    
    void set_value(vector<vector<long long>> &V){
        value = V;
    }
    
    void set_value(initializer_list<long long> list){
        auto it = list.begin();
        for(int i=0;i<get_height();i++){
            for(int j=0;j<get_width();j++){
                value[i][j]=*it;
                if(i!=get_height()-1||j!=get_width()-1)it++;
            }
        }
    }
    
    int get_width(){
        return value[0].size();
    }
    
    int get_height(){
        return value.size();
    }
    
    void print(){
        for(int i=0;i<get_height();i++){
            for(int j=0;j<get_width();j++){
                if(j!=0)cout<<' ';
                cout<<value[i][j];
            }
            cout<<endl;
        }
    }
    
};
matrix matrix_multiple(matrix &A,matrix &B){
    matrix R(A.get_height(),B.get_width());
    int multi_cnt;
    if(A.get_width()!=B.get_height()){
        assert(false);
    }
    else multi_cnt = A.get_width();
    
    for(int i=0;i<R.get_height();i++){
        for(int j=0;j<R.get_width();j++){
            R.value[i][j]=0;
            for(int k=0;k<multi_cnt;k++){
                
                R.value[i][j] = mod(R.value[i][j] + mod(A.value[i][k] * B.value[k][j]));
    
            }
        }
    }
    return R;
    
}
matrix matrix_beki(matrix A,long long cnt){
    if(A.get_width()!=A.get_height())assert(0);
    matrix R(A.get_width(),A.get_width());
    while(cnt!=0){
        if(cnt&1){
            R=matrix_multiple(R,A);
        }
        A=matrix_multiple(A,A);
        cnt>>=1;
    }
    return R;
}
int main(){
    int M,K;
    cin>>M>>K;
    
    vector<vector<long long>> X(M,vector<long long>(M,0));
    
    for(int i=0;i<M;i++){
        for(int j=0;j<M;j++){
            X[i][(i+j)%M]++;
            X[i][(i*j)%M]++;
        }
    }
    
    matrix P(M,M);
    P.set_value(X);
    
    vector<vector<long long>> Y(1,vector<long long>(M,0));
    Y[0][0] = 1;
    matrix Q(1,M);
    Q.set_value(Y);
    
    P = matrix_beki(P,K);
    Q = matrix_multiple(Q,P);
    
    cout<<Q.value[0][0]<<endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0