#589869 (C++17) No.1050 Zero (Maximum)

• 問題: No.1050 Zero (Maximum)
• ユーザー: tonegawa
• 提出日時: 2020-12-06 15:19:28
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 5,296 bytes
• コンパイル時間: 1,430 ms
• コンパイル使用メモリ: 137,400 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-09-17 13:07:06
• 合計ジャッジ時間: 1,973 ms
• ジャッジサーバーID （参考情報）: judge1 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	4 ms; 6,940 KB
testcase_03	AC	3 ms; 6,940 KB
testcase_04	AC	8 ms; 6,944 KB
testcase_05	AC	10 ms; 6,944 KB
testcase_06	AC	5 ms; 6,944 KB
testcase_07	AC	5 ms; 6,940 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	4 ms; 6,944 KB
testcase_10	AC	12 ms; 6,940 KB
testcase_11	AC	9 ms; 6,940 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	2 ms; 6,940 KB
testcase_14	AC	2 ms; 6,944 KB
testcase_15	AC	2 ms; 6,940 KB
testcase_16	AC	13 ms; 6,940 KB
testcase_17	AC	13 ms; 6,940 KB

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d, e) vector<vector<vector<e>>>(a, VV(b, c, d, e));
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
typedef std::vector<ll> v1;
typedef std::vector<v1> v2;
typedef std::vector<v2> v3;
using namespace std;

template<ll MOD>
struct StaticModMatrix{
private:
  using matrix = StaticModMatrix<MOD>;
  using vec = vector<uint64_t>;
  using mat = vector<vec>;
  static constexpr uint64_t init_neg(){
    uint64_t NEG = 0, s = 1, t = 0;
    for(int i=0;i<64;i++){
      if(~t & 1){
        t += MOD;
        NEG += s;
      }
      t >>= 1;
      s <<= 1;
    }
    return NEG;
  }
  static constexpr uint64_t init_r2(){
    uint64_t r2 = ((uint64_t)1<<32) % MOD;
    return r2 * r2 % MOD;
  }
  static constexpr uint64_t NEG_INV = init_neg();
  static constexpr uint64_t R2 = init_r2();
  static inline uint64_t generate(uint64_t x){
    return reduce(x * R2);
  }
  static inline uint64_t reduce(uint64_t x){
    x = (x + ((uint32_t)x * (uint32_t)NEG_INV) * MOD) >> 32;
    return x < MOD? x: x-MOD;
  }
  // (n, k) * (k, m) -> (n * m)
  // モンゴメリ乗算を使うと剰余演算を行う回数がN^3->N^2にできる
  // 乗算がボトルネックになりがちだけど定数倍が早いかわかんない
  static mat mul_mat(const mat &vl, const mat &vr){
    int N = vl.size(), K = vl[0].size(), M = vr[0].size();
    mat ret(N, vec(K, 0));
    for(int i=0;i<N;i++){
      for(int k=0;k<K;k++){
        //#pragma unroll(4)
        for(int j=0;j<M;j++){
          ret[i][j] += reduce(reduce(vl[i][k] * vr[k][j]));
        }
      }
      for(int j=0;j<M;j++) ret[i][j] = generate(ret[i][j]%MOD);
    }
    return ret;
  }
  // (n, m) + (n, m) -> (n, m)
  static mat add_mat(const mat &vl, const mat &vr){
    int N = vl.size(), M = vl[0].size();
    mat ret = vl;
    for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
        ret[i][j] = generate(reduce(ret[i][j]) + reduce(vr[i][j]));//?
      }
    }
    return ret;
  }
  // (n, m) - (n, m) -> (n, m)
  static mat sub_mat(const mat &vl, const mat &vr){
    int N = vl.size(), M = vl[0].size();
    mat ret = vl;
    for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
        ret[i][j] = generate(MOD + reduce(ret[i][j]) - reduce(vr[i][j]));//?
      }
    }
    return ret;
  }

  static mat mul_ll(const mat &vl, const ll vr){
    int N = vl.size(), M = vl[0].size();
    mat ret = vl;
    uint64_t x = generate(vr);
    for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
        ret[i][j] = reduce(reduce(ret[i][j] * x));
      }
    }
    return ret;
  }
  //n次の単位行列
  static mat eye(ll n){
    mat ret(n, vec(n, generate(0)));
    for(int i=0;i<n;i++) ret[i][i] = generate(1);
    return ret;
  }
  //vl^k (n, n) -> (n, n)  k>=2の場合正方行列じゃないと壊れる
  static mat pow_mat(const mat &vl, ll k){
    assert(vl.size()==vl[0].size());
    int N = vl.size();
    mat ret = eye(N), MUL = vl;
    while(k){
      if(k&1) ret = mul_mat(ret, MUL);
      k >>= 1;
      MUL = mul_mat(MUL, MUL);
    }
    return ret;
  }

  mat val;
public:
  int n, m;
  StaticModMatrix(){}
  StaticModMatrix(int n, int m, int x):val(n, vec(m, generate(x))), n(n), m(m){}
  StaticModMatrix(const mat &v):val(v), n(v.size()), m(v[0].size()){}
  StaticModMatrix(const vector<vector<ll>> &v):
    val(v.size(), vec(v[0].size())), n(v.size()), m(v[0].size()){
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) val[i][j] = generate(v[i][j]);
  }
  matrix operator +  (const matrix &vr){return           matrix(add_mat(this->val, vr.val));}
  matrix operator -  (const matrix &vr){return           matrix(sub_mat(this->val, vr.val));}
  matrix operator *  (const matrix &vr){return           matrix(mul_mat(this->val, vr.val));}
  matrix operator ^  (const ll      vr){return           matrix(pow_mat(this->val, vr));}
  matrix operator *  (const ll      vr){return           matrix(mul_ll(this->val, vr));}
  matrix operator += (const matrix &vr){return (*this) = matrix(add_mat(this->val, vr.val));}
  matrix operator -= (const matrix &vr){return (*this) = matrix(sub_mat(this->val, vr.val));}
  matrix operator *= (const matrix &vr){return (*this) = matrix(mul_mat(this->val, vr.val));}
  matrix operator ^= (const ll      vr){return (*this) = matrix(pow_mat(this->val, vr));}
  matrix operator *= (const ll      vr){return (*this) = matrix(mul_ll(this->val, vr));}

  inline ll access(int i, int j){return reduce(val[i][j]);}
  inline void write(int i, int j, ll x){val[i][j] = generate((x%MOD + MOD)%MOD);}
};

int main(){
  ll m, k;scanf("%lld %lld", &m,&k);
  using mat = StaticModMatrix<1000000007>;
  mat a(m, m, 0);
  for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
      int num = a.access(i, (i+j)%m);
      a.write(i, (i+j)%m, num+1);
      int num2 = a.access(i, (i*j)%m);
      a.write(i, (i*j)%m, num2+1);
    }
  }
  a ^= k;
  printf("%lld\n", a.access(0, 0));
}