結果

問題 No.963 門松列列(2)
ユーザー noshi91
提出日時 2019-12-14 22:45:59
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 464 ms
コード長 6,308 Byte
コンパイル時間 792 ms
使用メモリ 28,092 KB
最終ジャッジ日時 2020-01-18 20:56:12

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00small1.txt AC 0 ms
3,196 KB
00small2.txt AC 4 ms
3,168 KB
00small3.txt AC 4 ms
3,200 KB
00small4.txt AC 0 ms
3,324 KB
00small5.txt AC 4 ms
3,312 KB
rnd1.txt AC 220 ms
15,552 KB
rnd2.txt AC 24 ms
4,236 KB
rnd3.txt AC 216 ms
15,272 KB
rnd4.txt AC 452 ms
26,872 KB
rnd5.txt AC 460 ms
27,580 KB
xyz_largest.txt AC 464 ms
28,092 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <cstdint>

namespace n91 {

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  using value_type = u64;

  static constexpr u64 mod = Modulus;

private:
  static_assert(mod < static_cast<u64>(1) << 32,
                "Modulus must be less than 2**32");

  u64 v;

  constexpr modint &negate() noexcept {
    if (v != 0)
      v = mod - v;
    return *this;
  }

public:
  constexpr modint(const u64 x = 0) noexcept : v(x % mod) {}
  constexpr u64 &value() noexcept { return v; }
  constexpr const u64 &value() const noexcept { return v; }
  constexpr modint operator+() const noexcept { return modint(*this); }
  constexpr modint operator-() const noexcept { return modint(*this).negate(); }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    v += rhs.v;
    if (v >= mod)
      v -= mod;
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (v < rhs.v)
      v += mod;
    v -= rhs.v;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    v = v * rhs.v % mod;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = mod - 2;
    while (exp) {
      if (exp % 2 != 0)
        *this *= rhs;
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr bool operator==(const modint rhs) const noexcept {
    return v == rhs.v;
  }
  constexpr bool operator!=(const modint rhs) const noexcept {
    return v != rhs.v;
  }
};
template <std::uint_fast64_t Modulus>
constexpr typename modint<Modulus>::u64 modint<Modulus>::mod;

} // namespace n91
#include <functional>
#include <utility>

namespace n91 {

template <class T, class U, class Operate = std::multiplies<T>>
constexpr T power(T base, U exp, const Operate &oper = Operate(), T iden = 1) {
  while (exp != 0) {
    if (exp % 2 != 0) {
      iden = oper(iden, base);
    }
    exp /= 2;
    base = oper(base, base);
  }
  return iden;
}

} // namespace n91
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>

namespace n91 {

template <class T, class PrimitiveRoot>
std::vector<T> number_theoretic_transform(std::vector<T> a) {
  using usize = std::size_t;

  const usize size = a.size();
  const usize m = size - 1;
  std::vector<T> b(size);
  const T root = power(PrimitiveRoot::value, (T::mod - 1) / size);
  for (usize i = size; i != 1;) {
    i /= 2;
    std::swap(a, b);
    T c = 1;
    T d = root;
    for (usize j = 1; j != i; j *= 2)
      d *= d;
    for (usize j = 0; j != size; j += i) {
      const usize l = j * 2 & m;
      const usize r = l + i;
      for (usize k = 0; k != i; k += 1)
        a[j + k] = b[l + k] + b[r + k] * c;
      c *= d;
    }
  }
  return a;
}

template <class T, class PrimitiveRoot>
std::vector<T> inverse_number_theoretic_transform(std::vector<T> a) {
  a = number_theoretic_transform<T, PrimitiveRoot>(std::move(a));
  std::reverse(a.begin() + 1, a.end());
  const T inv = T::mod - (T::mod - 1) / a.size();
  for (T &e : a)
    e *= inv;
  return a;
}

} // namespace n91
#include <cstddef>
#include <utility>
#include <vector>

namespace n91 {

template <class T, class PrimitiveRoot>
class ntt_polynomial : public std::vector<T> {
  using Self = ntt_polynomial;
  using size_t = std::size_t;

public:
  template <class... Args>
  ntt_polynomial(Args &&... args)
      : std::vector<T>(std::forward<Args>(args)...) {}

  friend Self operator+(const Self &l, const Self &r) {
    const size_t n = std::min(l.size(), r.size());
    Self ret(n);
    for (size_t i = 0; i != n; ++i)
      ret[i] = l[i] + r[i];
    return ret;
  }
  friend Self operator-(const Self &l, const Self &r) {
    const size_t n = std::min(l.size(), r.size());
    Self ret(n);
    for (size_t i = 0; i != n; ++i)
      ret[i] = l[i] - r[i];
    return ret;
  }
  friend Self operator*(Self l, Self r) {
    if (l.size() > r.size())
      std::swap(l, r);
    const size_t n = l.size();
    size_t s = 1;
    while (s < 2 * n - 1)
      s *= 2;
    l.resize(s);
    l = number_theoretic_transform<T, PrimitiveRoot>(std::move(l));
    r.resize(n);
    r.resize(s);
    r = number_theoretic_transform<T, PrimitiveRoot>(std::move(r));
    for (size_t i = 0; i != s; ++i)
      l[i] *= r[i];
    l = inverse_number_theoretic_transform<T, PrimitiveRoot>(std::move(l));
    l.resize(n);
    l.shrink_to_fit();
    return l;
  }
  friend Self operator*(const T l, Self r) {
    for (T &e : r)
      e *= l;
    return r;
  }
  Self inverse() const {
    Self ret(1);
    ret[0] = static_cast<T>(1) / this->front();
    while (ret.size() < this->size()) {
      ret.resize(ret.size() * 2);
      ret = T(2) * ret - ret * ret * (*this);
    }
    ret.shrink_to_fit();
    return ret;
  }
};

} // namespace n91
namespace n91 {

template <class T, class U, U v> class constant_type {
public:
  using value_type = T;

  static constexpr T value = v;
};
template <class T, class U, U v> constexpr T constant_type<T, U, v>::value;

} // namespace n91

#include <cstdio>
#include <iostream>

int main() {
  using usize = std::size_t;
  using mint = n91::modint<1012924417>;
  using pr = n91::constant_type<mint, int, 5>;
  using poly = n91::ntt_polynomial<mint, pr>;

  usize n;
  std::cin >> n;
  poly sin(n + 1);

  {
    mint temp = 1;
    for (usize i = 0; i <= n; ++i) {
      if (i % 2 == 1) {
        sin[i] = static_cast<mint>(1) / temp;
        temp = -temp;
      }
      temp *= i + 1;
    }
    sin[0] += 1;
  }
  poly cos(n + 1);

  {
    mint temp = 1;
    for (usize i = 0; i <= n; ++i) {
      if (i % 2 == 0) {
        cos[i] = static_cast<mint>(1) / temp;
        temp = -temp;
      }
      temp *= i + 1;
    }
  }

  const auto ans = sin * cos.inverse();
  mint temp = 2;
  for (usize i = 1; i <= n; ++i)
    temp *= i;

  std::cout << (ans[n] * temp).value() << std::endl;
}
0