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

提出ソース

結果

問題	No.1050 Zero (Maximum)
ユーザー	tonegawa
提出日時	2020-12-06 15:35:59
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	5,277 bytes
コンパイル時間	1,466 ms
コンパイル使用メモリ	138,124 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-17 15:25:26
合計ジャッジ時間	4,102 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	WA	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	WA	-
testcase_17	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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(mat vl, 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 j=0;j<K;j++){
        vl[i][j] = generate(vl[i][j]);
      }
    }
    for(int i=0;i<K;i++){
      for(int j=0;j<M;j++){
        vr[i][j] = generate(vr[i][j]);
      }
    }
    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] %= 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] += vr[i][j];
        if(ret[i][j]>=MOD) ret[i][j] -= MOD;
      }
    }
    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] += MOD - vr[i][j];
        if(ret[i][j]>=MOD) ret[i][j] -= MOD;
      }
    }
    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(generate(ret[i][j]) * x));
      }
    }
    return ret;
  }
  //n次の単位行列
  static mat eye(ll n){
    mat ret(n, vec(n, 0));
    for(int i=0;i<n;i++) ret[i][i] = 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] = 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));}
  vec&   operator [] (const int i){return val[i];}
};

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++){
      a[i][(i+j>m?i+j-m:i+j)]++;
      a[i][(i*j)%m]++;
    }
  }
  a ^= k;
  printf("%lld\n", a[0][0]);
}

yukicoder

結果

テストケース

ソースコード