#103395 (C++11) No.303 割れません

• 問題: No.303 割れません
• ユーザー: yuppe19 😺
• 提出日時: 2016-07-14 17:10:26
• 言語: C++11 (gcc 11.4.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 11,332 bytes
• コンパイル時間: 457 ms
• コンパイル使用メモリ: 63,880 KB
• 最終ジャッジ日時: 2024-04-27 02:21:29
• 合計ジャッジ時間: 882 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

コンパイルメッセージ

main.cpp:34:3: error: ‘vector’ does not name a type
   34 |   vector<i64> v;
      |   ^~~~~~
main.cpp:39:10: error: ‘vector’ does not name a type
   39 |   inline vector<i64> karatsuba(const vector<i64>&, const vector<i64>&) const;
      |          ^~~~~~
main.cpp:45:30: error: ‘vector’ has not been declared
   45 |   static void fmt(const int, vector<i64>*);
      |                              ^~~~~~
main.cpp:45:36: error: expected ‘,’ or ‘...’ before ‘<’ token
   45 |   static void fmt(const int, vector<i64>*);
      |                                    ^
main.cpp:46:31: error: ‘vector’ has not been declared
   46 |   static void ifmt(const int, vector<i64>*);
      |                               ^~~~~~
main.cpp:46:37: error: expected ‘,’ or ‘...’ before ‘<’ token
   46 |   static void ifmt(const int, vector<i64>*);
      |                                     ^
main.cpp:47:33: error: ‘vector’ has not been declared
   47 |   static void convol(const int, vector<i64>*, vector<i64>*);
      |                                 ^~~~~~
main.cpp:47:39: error: expected ‘,’ or ‘...’ before ‘<’ token
   47 |   static void convol(const int, vector<i64>*, vector<i64>*);
      |                                       ^
main.cpp:52:32: error: ‘vector’ has not been declared
   52 |   static void myfmt(const int, vector<i64>*, const bool);
      |                                ^~~~~~
main.cpp:52:38: error: expected ‘,’ or ‘...’ before ‘<’ token
   52 |   static void myfmt(const int, vector<i64>*, const bool);
      |                                      ^
main.cpp:89:33: error: ‘vector’ has not been declared
   89 | void FMT::myfmt(const int logn, vector<i64> *a, const bool inv) {
      |                                 ^~~~~~
main.cpp:89:39: error: expected ‘,’ or ‘...’ before ‘<’ token
   89 | void FMT::myfmt(const int logn, vector<i64> *a, const bool inv) {
      |                         

ソースコード

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
using i64 = long long;

constexpr int BASE_DIGITS = 4;
constexpr int BASE = 10000;
struct bigint {
  bigint(void);
  bigint(const int size);
  bigint(const string val);
  bigint(const i64 val);
  static bigint valueOf(const i64);
  bigint& abs(bigint&);
  bigint& operator = (const bigint&);
  bigint operator + (const bigint&) const;
  bigint operator - () const;
  bigint operator - (const bigint&) const;
  bigint operator * (const bigint&) const;
  bigint& operator += (const bigint&);
  bigint& operator -= (const bigint&);
  bigint& operator *= (const bigint&);
  bool operator <  (bigint&);
  bigint pow(const int) const;
  int countTrailingZeros(void) const;
  friend bigint factorial2(const int);
  friend bigint factorial(const int);
  friend bigint naive_factorial(const int);
  friend ostream& operator << (ostream&, const bigint&);
private:
  int minus;
  int n; // vの要素数
  vector<i64> v;
  inline bool absGreater(const bigint&, const bigint&) const;
  inline bigint add(const bigint&, const bigint&) const;
  inline bigint sub(const bigint&, const bigint&) const;
  inline bigint fftmul(const bigint&, const bigint&) const;
  inline vector<i64> karatsuba(const vector<i64>&, const vector<i64>&) const;
  inline bigint karatsuba(const bigint&, const bigint&) const;
  static bigint pow(const bigint&, const bigint&, const int);
};

struct FMT {
  static void fmt(const int, vector<i64>*);
  static void ifmt(const int, vector<i64>*);
  static void convol(const int, vector<i64>*, vector<i64>*);
private:
  static constexpr i64 N = 5LL << 37;
  static constexpr i64 O = 2003LL;
  static constexpr i64 M = N * 211 + 1;
  static void myfmt(const int, vector<i64>*, const bool);
};

inline i64 mod_mul(const i64 x, const i64 y, const i64 m) {
  // yとmの最大ビット長はともに48ビット。
  // http://codeforces.com/blog/entry/15884
  // 12 < floor(63 - log2(MAX_VALUE)) = 15
  // 0xfff = (1<<12) - 1
  i64 b, res = y * (x & 0xfff);
  res += (b=(y<<12) % m) * ((x>>12) & 0xfff);
  res += (b=(b<<12) % m) * ((x>>24) & 0xfff);
  res += (b<<12) % m     * ((x>>36) & 0xfff);
  res %= m;
  return res;
}

inline tuple<i64, i64, i64> extgcd(const i64 x, const i64 y) {
  if(y == 0) { return make_tuple(1LL, 0LL, x); }
  i64 a, b, d; tie(a, b, d) = extgcd(y, x%y);
  return make_tuple(b, a-x/y*b, d);
}

inline i64 mod_inv(const i64 a, const i64 m) {
  i64 x, _, d; tie(x, _, d) = extgcd(a, m);
  return (x % m + m) % m;
}

inline i64 mod_pow(const i64 a, const i64 r, const i64 n, const i64 m) {
  if(n == 0) { return r; }
  if(n & 1)  { return mod_pow(a, mod_mul(a, r, m), n-1, m); }
  return mod_pow(mod_mul(a, a, m), r, n>>1, m);
}

inline i64 mod_pow(const i64 a, const i64 n, const i64 m) {
  return mod_pow(a, 1, n, m);
}

void FMT::myfmt(const int logn, vector<i64> *a, const bool inv) {
  const int n = 1 << logn;
  for(int H=1, W=n>>1; H<n; H<<=1, W>>=1) {
    vector<i64> y = *a;
    i64 r = mod_pow(O, N/(H*2), M);
    if(inv) { r = mod_inv(r, M); }
    i64 w = 1;
    for(int k=0; k<H; ++k) {
      for(int j=0; j<W; ++j) {
        i64 y0 = y[2*W*k+j],
            y1 = mod_mul(y[2*W*k+j+W], w, M);
        a->at(W* k   +j) = y0 + y1 < M ? y0 + y1     : y0 + y1 - M;
        a->at(W*(k+H)+j) = y0 < y1     ? y0 - y1 + M : y0 - y1;
      }
      w = mod_mul(w, r, M);
    }
  }
}

void FMT::fmt(const int logn, vector<i64> *a) {
  myfmt(logn, a, false);
}

void FMT::ifmt(const int logn, vector<i64> *a) {
  myfmt(logn, a, true);
  int n = 1 << logn;
  i64 inv = mod_inv(n, M);
  for(int i=0; i<n; ++i) {
    a->at(i) = mod_mul(a->at(i), inv, M);
  }
}

void FMT::convol(const int logn, vector<i64> *a, vector<i64> *b) {
  fmt(logn, a);
  fmt(logn, b);
  for(int i=0; i<1<<logn; ++i) {
    a->at(i) = mod_mul(a->at(i), b->at(i), M);
  }
  ifmt(logn, a);
}

bigint::bigint(void) {}

bigint::bigint(const int size) {
  n = size;
  v.assign(size, 0LL);
}

bigint::bigint(const string s) {
  minus = s[0] == '-';
  int last = s.size();
  int m = last - minus; // 桁数
  n = (m + BASE_DIGITS - 1) / BASE_DIGITS;
  v.assign(n, 0LL);
  for(int i=last-1, k=0; i>=minus; i-=BASE_DIGITS, ++k) {
    for(int j=max(minus, i-BASE_DIGITS+1); j<=i; ++j) {
      v[k] = v[k] * 10 + s[j] - '0';
    }
  }
  if(v[n-1] == 0) { minus = false; } // -0にはしない
}

bigint::bigint(const i64 x) {
  *this = bigint::valueOf(x);
}

bigint bigint::valueOf(const i64 x) {
  constexpr int N = 5;
  bigint res(N);
  res.minus = x < 0;
  i64 y = x;
  for(int i=0; i<N; ++i) {
    int z = y % BASE;
    res.v[i] = ::abs(y % BASE);
    y /= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  if(res.v[res.n-1] == 0) { res.minus = false; } // -0にはしない
  return res;
}

bigint& bigint::operator = (const bigint &other) {
  minus = other.minus;
  n = other.n;
  v = other.v;
  return *this;
}

bool bigint::absGreater(const bigint& a, const bigint& b) const {
  if(a.n != b.n) { return a.n < b.n; }
  for(int i=a.n-1; i>=0; --i) {
    if(a.v[i] != b.v[i]) { return a.v[i] < b.v[i]; }
  }
  return false; // abs(a) == abs(b)のときはfalseを返す
}

bool bigint::operator < (bigint& other) {
  if(minus != other.minus) { return minus; }
  return absGreater(*this, other) ^ minus;
}

bigint bigint::add(const bigint& a, const bigint& b) const {
  int size = max(a.n, b.n) + 1;
  bigint res(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] += b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] >= BASE) { // 繰り上がり
      ++res.v[i+1];
      res.v[i] -= BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint& bigint::abs(bigint& a) {
  a.minus = false;
  return a;
}

bigint bigint::sub(const bigint& a, const bigint& b) const {
  int size = max(a.n, b.n) + 1;
  bigint res(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] -= b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] < 0) { // 借りてくる
      --res.v[i+1];
      res.v[i] += BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint bigint::operator + (const bigint& other) const {
  bigint res;
  if(minus == other.minus) { // +, + or -, -
    res = add(*this, other);
    res.minus = minus;
  } else if(absGreater(*this, other)) { // +, - or -, +
    res = sub(other, *this);
    res.minus = other.minus;
  } else {
    res = sub(*this, other);
    res.minus = minus;
  }
  if(res.n == 1 && res.v[0] == 0) { res.minus = false; }
  return res;
}

bigint bigint::operator - () const {
  bigint obj = *this;
  obj.minus = !minus;
  return obj;
}

bigint bigint::operator - (const bigint& other) const {
  return *this + (-other);
}

bigint bigint::fftmul(const bigint& a, const bigint& b) const {
  int size = max(a.n, b.n) * 2;
  int m; for(m=0; 1<<m < size; ++m) /* nop */ ;
  bigint res(1<<m);
  vector<i64> c(1<<m, 0);
  for(int i=0; i<a.n; ++i) { res.v[i] = a.v[i]; }
  for(int i=0; i<b.n; ++i) { c[i]     = b.v[i]; }
  FMT::convol(m, &res.v, &c);
  for(int i=0; i<(1<<m)-1; ++i) {
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = a.minus ^ b.minus;
  return res;
}

vector<i64> bigint::karatsuba(const vector<i64>& a, const vector<i64>& b) const {
  int n = a.size();
  vector<i64> res(n + n);
  if(n <= 32) {
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) res[i+j] += a[i] * b[j];
    return res;
  }
  int k = n >> 1;
  vector<i64> a1(a.begin(), a.begin() + k),
              a2(a.begin() + k, a.end()),
              b1(b.begin(), b.begin() + k),
              b2(b.begin() + k, b.end()),
              a1b1 = karatsuba(a1, b1),
              a2b2 = karatsuba(a2, b2);
  for(int i=0; i<k; ++i) { a2[i] += a1[i]; b2[i] += b1[i]; }
  vector<i64> r = karatsuba(a2, b2);
  for(int i=0, m=a1b1.size(); i<m; ++i) { r[i]     -= a1b1[i]; }
  for(int i=0, m=a2b2.size(); i<m; ++i) { r[i]     -= a2b2[i]; }
  for(int i=0, m=r.size();    i<m; ++i) { res[i+k] += r[i]; }
  for(int i=0, m=a1b1.size(); i<m; ++i) { res[i]   += a1b1[i]; }
  for(int i=0, m=a2b2.size(); i<m; ++i) { res[i+n] += a2b2[i]; }
  return res;
}

bigint bigint::karatsuba(const bigint& ba, const bigint& bb) const {
  vector<i64> a(ba.v.begin(), ba.v.end()),
              b(bb.v.begin(), bb.v.end());
  int size = max(ba.n, bb.n);
  int m; for(m=0 ; 1<<m < size; ++m) /* nop */ ;
  a.resize(1<<m); b.resize(1<<m);
  vector<i64> c = karatsuba(a, b);
  int cn = c.size();
  bigint res(cn);
  for(int i=0; i<cn-1; ++i) {
    res.v[i]   += c[i];
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = ba.minus ^ bb.minus;
  return res;
}

bigint bigint::operator * (const bigint& other) const {
  return max(n, other.n) < 1000 ? karatsuba(*this, other) : fftmul(*this, other);
}

bigint& bigint::operator += (const bigint& other) {
  *this = *this + other;
  return *this;
}

bigint& bigint::operator -= (const bigint& other) {
  *this = *this - other;
  return *this;
}

bigint& bigint::operator *= (const bigint& other) {
  *this = *this * other;
  return *this;
}

bigint bigint::pow(const bigint &x, const bigint &r, const int n) {
  if(n == 0) { return r; }
  if(n & 1)  { return pow(x, r*x, n-1); }
  return pow(x*x, r, n>>1);
}

bigint bigint::pow(const int n) const {
  return bigint::pow(*this, bigint::valueOf(1LL), n);
}

inline bigint recfact(const int start, const int n) {
  if(n <= 2) {
    bigint r = bigint::valueOf(start);
    for(int i=start+1; i<start+n; ++i) { r *= bigint::valueOf(i); }
    return r;
  }
  int i = n / 2;
  return recfact(start, i) * recfact(start+i, n-i);
}

inline bigint factorial(const int n) {
  return recfact(1, n);
}

ostream& operator << (ostream &stream, const bigint &a) {
  if(a.minus) { stream << '-'; }
  stream << a.v[a.n-1];
  for(int i=a.n-2; i>=0; --i) {
    stream << setw(BASE_DIGITS) << setfill('0') << a.v[i];
  }
  return stream;
}

const bigint *bigzero = new bigint(0LL),
             *bigone  = new bigint(1LL),
             *bigtwo  = new bigint(2LL);

inline vector<bigint> matmul(const vector<bigint> &A, const vector<bigint> &B) {
  return {
    A[0]*B[0] + A[1]*B[2],
    A[0]*B[1] + A[1]*B[3],
    A[2]*B[0] + A[3]*B[2],
    A[2]*B[1] + A[3]*B[3]
  };
}

inline vector<bigint> matpow(const vector<bigint> &A, const vector<bigint> &R, const i64 n) {
  if(n == 0) { return R; }
  if(n & 1)  { return matpow(A, matmul(R, A), n-1); }
  return matpow(matmul(A, A), R, n>>1);
}

inline vector<bigint> matpow(const vector<bigint> &A, const i64 n) {
  return matpow(A, {*bigone, *bigzero, *bigzero, *bigone}, n);
}

inline bigint fibo_mat(int n) {
  vector<bigint> A = {*bigone, *bigone, *bigone, *bigzero};
  return matpow(A, n-1)[0];
}

int main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  int L; cin >> L;
  if(L == 2) {
    cout << "3" << '\n';
    cout << "INF" << '\n';
    return 0;
  }
  bigint res = fibo_mat(L);
  if(!(L & 1)) {
    bigint x = fibo_mat(L/2);
    res -= x * x;
  }
  cout << L << '\n';
  cout << res << '\n';
  return 0;
}