結果

問題 No.1050 Zero (Maximum)
コンテスト
ユーザー tonegawa
提出日時 2020-12-06 15:35:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 5,277 bytes
コンパイル時間 1,519 ms
コンパイル使用メモリ 134,112 KB
最終ジャッジ日時 2025-01-16 18:26:27
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 RE * 1
other AC * 3 WA * 4 RE * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:175:14: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long unsigned int>, long unsigned int>::value_type’ {aka ‘long unsigned int’} [-Wformat=]
  175 |   printf("%lld\n", a[0][0]);
      |           ~~~^
      |              |
      |              long long int
      |           %ld
main.cpp:165:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |   ll m, k;scanf("%lld %lld", &m,&k);
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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]);
}
0