結果

問題 No.963 門松列列（2）
ユーザー risujirohrisujiroh
提出日時 2020-01-05 21:44:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 288 ms / 3,000 ms
コード長 6,937 bytes
コンパイル時間 2,229 ms
コンパイル使用メモリ 183,572 KB
実行使用メモリ 18,112 KB
最終ジャッジ日時 2024-11-22 23:33:01
合計ジャッジ時間 3,815 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 138 ms
10,836 KB
testcase_06 AC 16 ms
5,248 KB
testcase_07 AC 135 ms
10,324 KB
testcase_08 AC 280 ms
16,612 KB
testcase_09 AC 282 ms
17,336 KB
testcase_10 AC 288 ms
18,112 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