結果

問題 No.1050 Zero (Maximum)
コンテスト
ユーザー queee
提出日時 2020-05-08 22:47:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,784 bytes
コンパイル時間 901 ms
コンパイル使用メモリ 81,276 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 01:04:01
合計ジャッジ時間 1,743 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; using ll=long long; const ll LNF=1e18; const int INF = 1e9+1; const ll M = 1e9+7;
typedef pair<int,int> P;

struct mat {
  vector<vector<ll>> v, v2;
  vector<ll> an, an2; int n;
  mat(int _n) : n(_n) {
    v.resize(n);
    for(int i=0;i<n;i++) v[i].resize(n);
    v2.resize(n);
    for(int i=0;i<n;i++) v2[i].resize(n);
    an.resize(n); an2.resize(n);
  }
  void initialize() {
    // 各自で調整
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        v[i][j]++;
      }
    }
    
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        v[i][i*j%n]++;
      }
    }

    an[0]=1;
  }
  void update() {
    //cout << "Updating...";
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++)
        v2[i][j]=0;
      //v2[i].assign(n, 0LL);
    }

    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        for(int k=0;k<n;k++) {
          v2[i][j] += v[i][k] * v[k][j] % M;
        }
        v2[i][j] %= M;
      }
    }

    v=v2;
    //cout << "Done!" << endl;
  }
  void update_ans() {
    //an2.assign(n, 0LL);
    for(int i=0;i<n;i++) {
      an2[i]=0;
    }
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        an2[i] += v[i][j] * an[j] % M;
      }
      an2[i] %= M;
    }
    an=an2;
  }
  void solve(ll x) {
    // x乗
    while(x>0) {
      if (x&1) update_ans();
      update();
      x>>=1;
    }
  }

  void print() {
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        cout << v[i][j]<<" ";
      } cout << endl;
    }

    for(int i=0;i<n;i++) {
      cout<<an[i]<<" ";
    } cout<<endl<<endl;
  }
};

int main() {
  ll m,k; cin>>m>>k;
  mat ma(m);
  ma.initialize();
  //ma.print();
  ma.solve(k);
  //ma.print();
  cout<<ma.an[0]<<endl;
}
0