結果

問題 No.963 門松列列(2)
ユーザー risujiroh
提出日時 2020-01-05 21:44:52
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 404 ms
コード長 6,937 Byte
コンパイル時間 1,956 ms
使用メモリ 17,592 KB
最終ジャッジ日時 2020-01-05 21:44:57

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00small1.txt AC 0 ms
3,356 KB
00small2.txt AC 4 ms
3,352 KB
00small3.txt AC 0 ms
3,376 KB
00small4.txt AC 4 ms
3,368 KB
00small5.txt AC 0 ms
3,272 KB
rnd1.txt AC 140 ms
10,496 KB
rnd2.txt AC 16 ms
3,680 KB
rnd3.txt AC 136 ms
9,988 KB
rnd4.txt AC 280 ms
16,332 KB
rnd5.txt AC 280 ms
16,776 KB
xyz_largest.txt AC 404 ms
17,592 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

template <class T> vector<T> operator-(vector<T> a) {
  for (auto&& e : a) e = -e;
  return a;
}
template <class T> vector<T>& operator+=(vector<T>& l, const vector<T>& r) {
  l.resize(max(l.size(), r.size()));
  for (int i = 0; i < (int)r.size(); ++i) l[i] += r[i];
  return l;
}
template <class T> vector<T> operator+(vector<T> l, const vector<T>& r) {
  return l += r;
}
template <class T> vector<T>& operator-=(vector<T>& l, const vector<T>& r) {
  l.resize(max(l.size(), r.size()));
  for (int i = 0; i < (int)r.size(); ++i) l[i] -= r[i];
  return l;
}
template <class T> vector<T> operator-(vector<T> l, const vector<T>& r) {
  return l -= r;
}
template <class T> vector<T> operator*(const vector<T>& l, const vector<T>& r) {
  if (l.empty() or r.empty()) return {};
  vector<T> res(l.size() + r.size() - 1);
  for (int i = 0; i < (int)l.size(); ++i)
    for (int j = 0; j < (int)r.size(); ++j) res[i + j] += l[i] * r[j];
  return res;
}
template <class T> vector<T>& operator*=(vector<T>& l, const vector<T>& r) {
  return l = l * r;
}
template <class T> vector<T> inverse(const vector<T>& a) {
  assert(not a.empty() and not (a[0] == 0));
  vector<T> b{1 / a[0]};
  while (b.size() < a.size()) {
    vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size()));
    x *= b * b;
    b.resize(2 * b.size());
    for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = -x[i];
  }
  b.resize(a.size());
  return b;
}
template <class T> vector<T> operator/(vector<T> l, vector<T> r) {
  if (l.size() < r.size()) return {};
  reverse(begin(l), end(l)), reverse(begin(r), end(r));
  int n = l.size() - r.size() + 1;
  l.resize(n), r.resize(n);
  l *= inverse(r);
  return {rend(l) - n, rend(l)};
}
template <class T> vector<T>& operator/=(vector<T>& l, const vector<T>& r) {
  return l = l / r;
}
template <class T> vector<T> operator%(vector<T> l, const vector<T>& r) {
  if (l.size() < r.size()) return l;
  l -= l / r * r;
  l.resize(r.size() - 1);
  return l;
}
template <class T> vector<T>& operator%=(vector<T>& l, const vector<T>& r) {
  return l = l % r;
}
template <class T> vector<T> derivative(const vector<T>& a) {
  vector<T> res(max((int)a.size() - 1, 0));
  for (int i = 0; i < (int)res.size(); ++i) res[i] = (i + 1) * a[i + 1];
  return res;
}
template <class T> vector<T> primitive(const vector<T>& a) {
  vector<T> res(a.size() + 1);
  for (int i = 1; i < (int)res.size(); ++i) res[i] = a[i - 1] / i;
  return res;
}
template <class T> vector<T> logarithm(const vector<T>& a) {
  assert(not a.empty() and a[0] == 1);
  auto res = primitive(derivative(a) * inverse(a));
  res.resize(a.size());
  return res;
}
template <class T> vector<T> exponent(const vector<T>& a) {
  assert(a.empty() or a[0] == 0);
  vector<T> b{1};
  while (b.size() < a.size()) {
    vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size()));
    x[0] += 1;
    b.resize(2 * b.size());
    x -= logarithm(b);
    x *= {begin(b), begin(b) + b.size() / 2};
    for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = x[i];
  }
  b.resize(a.size());
  return b;
}

template <class T, class F = multiplies<T>>
T power(T a, long long n, F op = multiplies<T>(), T e = 1) {
  assert(n >= 0);
  T res = e;
  while (n) {
    if (n & 1) res = op(res, a);
    if (n >>= 1) a = op(a, a);
  }
  return res;
}

template <unsigned Mod> struct Modular {
  using M = Modular;
  unsigned v;
  Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {}
  M operator-() const { return M() -= *this; }
  M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; }
  M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; }
  M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; }
  M& operator/=(M r) { return *this *= power(r, Mod - 2); }
  friend M operator+(M l, M r) { return l += r; }
  friend M operator-(M l, M r) { return l -= r; }
  friend M operator*(M l, M r) { return l *= r; }
  friend M operator/(M l, M r) { return l /= r; }
  friend bool operator==(M l, M r) { return l.v == r.v; }
};

template <unsigned Mod> void ntt(vector<Modular<Mod>>& a, bool inverse) {
  static vector<Modular<Mod>> dt(30), idt(30);
  if (dt[0] == 0) {
    Modular<Mod> root = 2;
    while (power(root, (Mod - 1) / 2) == 1) root += 1;
    for (int i = 0; i < 30; ++i)
      dt[i] = -power(root, (Mod - 1) >> (i + 2)), idt[i] = 1 / dt[i];
  }
  int n = a.size();
  assert((n & (n - 1)) == 0);
  if (not inverse) {
    for (int w = n; w >>= 1; ) {
      Modular<Mod> t = 1;
      for (int s = 0, k = 0; s < n; s += 2 * w) {
        for (int i = s, j = s + w; i < s + w; ++i, ++j) {
          auto x = a[i], y = a[j] * t;
          if (x.v >= Mod) x.v -= Mod;
          a[i].v = x.v + y.v, a[j].v = x.v + (Mod - y.v);
        }
        t *= dt[__builtin_ctz(++k)];
      }
    }
  } else {
    for (int w = 1; w < n; w *= 2) {
      Modular<Mod> t = 1;
      for (int s = 0, k = 0; s < n; s += 2 * w) {
        for (int i = s, j = s + w; i < s + w; ++i, ++j) {
          auto x = a[i], y = a[j];
          a[i] = x + y, a[j].v = x.v + (Mod - y.v), a[j] *= t;
        }
        t *= idt[__builtin_ctz(++k)];
      }
    }
  }
}
template <unsigned Mod>
vector<Modular<Mod>> operator*(vector<Modular<Mod>> l, vector<Modular<Mod>> r) {
  if (l.empty() or r.empty()) return {};
  int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1);
  if (min(n, m) < 30) {
    vector<long long> res(n + m- 1);
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) 
      res[i + j] += (l[i] * r[j]).v;
    return {begin(res), end(res)};
  }
  bool eq = l == r;
  l.resize(sz), ntt(l, false);
  if (eq) r = l;
  else r.resize(sz), ntt(r, false);
  for (int i = 0; i < sz; ++i) l[i] *= r[i];
  ntt(l, true), l.resize(n + m - 1);
  auto isz = 1 / Modular<Mod>(sz);
  for (auto&& e : l) e *= isz;
  return l;
}

constexpr long long mod = 1012924417;
using Mint = Modular<mod>;

vector<Mint> fact, inv_fact;
void prepare_fact(int n) {
  fact.resize(n + 1), inv_fact.resize(n + 1);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fact[i] = i * fact[i - 1];
  }
  inv_fact[n] = 1 / fact[n];
  for (int i = n; i; --i) {
    inv_fact[i - 1] = i * inv_fact[i];
  }
}
Mint binom(int n, int k) {
  if (k < 0 or k > n) return 0;
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  prepare_fact(n + 2);
  // 2 * (1 + tan(X / 2)) / (1 - tan(X / 2))
  vector<Mint> b(n + 2); // B_n / n!
  for (int i = 0; i <= n + 1; ++i) {
    b[i] = inv_fact[i + 1];
  }
  b = inverse(b);
  vector<Mint> tanx2(n + 1);
  for (int i = 1; 2 * i - 1 <= n; ++i) {
    tanx2[2 * i - 1] = power(-1, i - 1) * 2 * (power(Mint(2), 2 * i) - 1) * b[2 * i];
  }
  auto f = vector<Mint>{2} * (vector<Mint>{1} + tanx2) * inverse(vector<Mint>{1} - tanx2);
  auto res = f[n] * fact[n];
  cout << res.v << '\n';
}
0