#1087007 (C++23) No.1879 How many matchings?

提出ソース
結果

問題	No.1879 How many matchings?
コンテスト
ユーザー	kusaf_
提出日時	2025-05-21 11:02:23
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	14,603 bytes
コンパイル時間	4,116 ms
コンパイル使用メモリ	285,656 KB
実行使用メモリ	7,844 KB
最終ジャッジ日時	2025-05-21 11:02:28
合計ジャッジ時間	4,522 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 15
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

#include <cassert>
#include <numeric>
#include <type_traits>

#ifdef _MSC_VER
#include <intrin.h>
#endif


#include <utility>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

constexpr long long safe_mod(long long x, long long m) {
  x %= m;
  if(x < 0) { x += m; }
  return x;
}

struct barrett {
  unsigned int _m;
  unsigned long long im;
  explicit barrett(unsigned int m): _m(m), im((unsigned long long)(-1) / m + 1) {}
  unsigned int umod() const { return _m; }
  unsigned int mul(unsigned int a, unsigned int b) const {
    unsigned long long z = a;
    z *= b;
#ifdef _MSC_VER
    unsigned long long x;
    _umul128(z, im, &x);
#else
    unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
    unsigned long long y = x * _m;
    return (unsigned int)(z - y + (z < y ? _m : 0));
  }
};

constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
  if(m == 1) { return 0; }
  unsigned int _m = (unsigned int)(m);
  unsigned long long r = 1;
  unsigned long long y = safe_mod(x, m);
  while(n) {
    if(n & 1) { r = (r * y) % _m; }
    y = (y * y) % _m;
    n >>= 1;
  }
  return r;
}

constexpr bool is_prime_constexpr(int n) {
  if(n <= 1) { return false; }
  if(n == 2 || n == 7 || n == 61) { return true; }
  if(n % 2 == 0) { return false; }
  long long d = n - 1;
  while(d % 2 == 0) d /= 2;
  constexpr long long bases[3] = {2, 7, 61};
  for(long long a : bases) {
    long long t = d;
    long long y = pow_mod_constexpr(a, t, n);
    while(t != n - 1 && y != 1 && y != n - 1) {
      y = y * y % n;
      t <<= 1;
    }
    if(y != n - 1 && t % 2 == 0) { return false; }
  }
  return true;
}
template<int n> constexpr bool is_prime = is_prime_constexpr(n);

constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
  a = safe_mod(a, b);
  if(a == 0) return {b, 0};
  long long s = b, t = a;
  long long m0 = 0, m1 = 1;
  while(t) {
    long long u = s / t;
    s -= t * u;
    m0 -= m1 * u;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if(m0 < 0) { m0 += b / s; }
  return {s, m0};
}

constexpr int primitive_root_constexpr(int m) {
  if(m == 2) { return 1; }
  if(m == 167772161) { return 3; }
  if(m == 469762049) { return 3; }
  if(m == 754974721) { return 11; }
  if(m == 998244353) { return 3; }
  int divs[20] = {};
  divs[0] = 2;
  int cnt = 1;
  int x = (m - 1) / 2;
  while(x % 2 == 0) { x /= 2; }
  for(int i = 3; (long long)(i)*i <= x; i += 2) {
    if(x % i == 0) {
      divs[cnt++] = i;
      while(x % i == 0) { x /= i; }
    }
  }
  if(x > 1) { divs[cnt++] = x; }
  for(int g = 2;; g++) {
    bool ok = true;
    for(int i = 0; i < cnt; i++) {
      if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
        ok = false;
        break;
      }
    }
    if(ok) { return g; }
  }
}
template<int m> constexpr int primitive_root = primitive_root_constexpr(m);

unsigned long long floor_sum_unsigned(unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b) {
  unsigned long long ans = 0;
  while(true) {
    if(a >= m) {
      ans += n * (n - 1) / 2 * (a / m);
      a %= m;
    }
    if(b >= m) {
      ans += n * (b / m);
      b %= m;
    }
    unsigned long long y_max = a * n + b;
    if(y_max < m) break;
    n = (unsigned long long)(y_max / m);
    b = (unsigned long long)(y_max % m);
    std::swap(m, a);
  }
  return ans;
}

}  // namespace internal

}  // namespace atcoder


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;

#else

template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;

#endif

template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

namespace internal {

struct modint_base {
};
struct static_modint_base : modint_base {
};

template<class T> using is_modint = std::is_base_of<modint_base, T>;
template<class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template<int m, std::enable_if_t<(1 <= m)> * = nullptr>
struct static_modint : internal::static_modint_base {
  using mint = static_modint;

 public:
  static constexpr int mod() { return m; }
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  static_modint(): _v(0) {}
  template<class T, internal::is_signed_int_t<T> * = nullptr>
  static_modint(T v) {
    long long x = (long long)(v % (long long)(umod()));
    if(x < 0) { x += umod(); }
    _v = (unsigned int)(x);
  }
  template<class T, internal::is_unsigned_int_t<T> * = nullptr>
  static_modint(T v) { _v = (unsigned int)(v % umod()); }
  unsigned int val() const { return _v; }
  mint &operator++() {
    _v++;
    if(_v == umod()) { _v = 0; }
    return *this;
  }
  mint &operator--() {
    if(_v == 0) { _v = umod(); }
    _v--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint &operator+=(const mint &rhs) {
    _v += rhs._v;
    if(_v >= umod()) { _v -= umod(); }
    return *this;
  }
  mint &operator-=(const mint &rhs) {
    _v -= rhs._v;
    if(_v >= umod()) { _v += umod(); }
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
  mint operator+() const { return *this; }
  mint operator-() const { return mint() - *this; }
  mint pow(long long n) const {
    assert(0 <= n);
    mint x = *this, r = 1;
    while(n) {
      if(n & 1) { r *= x; }
      x *= x;
      n >>= 1;
    }
    return r;
  }
  mint inv() const {
    if(prime) {
      assert(_v);
      return pow(umod() - 2);
    }
    else {
      auto eg = internal::inv_gcd(_v, m);
      assert(eg.first == 1);
      return eg.second;
    }
  }
  friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
  friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
  friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
  friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
  friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
  friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }

 private:
  unsigned int _v;
  static constexpr unsigned int umod() { return m; }
  static constexpr bool prime = internal::is_prime<m>;
};

template<int id> struct dynamic_modint : internal::modint_base {
  using mint = dynamic_modint;

 public:
  static int mod() { return (int)(bt.umod()); }
  static void set_mod(int m) {
    assert(1 <= m);
    bt = internal::barrett(m);
  }
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  dynamic_modint(): _v(0) {}
  template<class T, internal::is_signed_int_t<T> * = nullptr>
  dynamic_modint(T v) {
    long long x = (long long)(v % (long long)(mod()));
    if(x < 0) { x += mod(); }
    _v = (unsigned int)(x);
  }
  template<class T, internal::is_unsigned_int_t<T> * = nullptr>
  dynamic_modint(T v) {
    _v = (unsigned int)(v % mod());
  }
  unsigned int val() const { return _v; }
  mint &operator++() {
    _v++;
    if(_v == umod()) { _v = 0; }
    return *this;
  }
  mint &operator--() {
    if(_v == 0) { _v = umod(); }
    _v--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint &operator+=(const mint &rhs) {
    _v += rhs._v;
    if(_v >= umod()) { _v -= umod(); }
    return *this;
  }
  mint &operator-=(const mint &rhs) {
    _v += mod() - rhs._v;
    if(_v >= umod()) { _v -= umod(); }
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    _v = bt.mul(_v, rhs._v);
    return *this;
  }
  mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
  mint operator+() const { return *this; }
  mint operator-() const { return mint() - *this; }
  mint pow(long long n) const {
    assert(0 <= n);
    mint x = *this, r = 1;
    while(n) {
      if(n & 1) { r *= x; }
      x *= x;
      n >>= 1;
    }
    return r;
  }
  mint inv() const {
    auto eg = internal::inv_gcd(_v, mod());
    assert(eg.first == 1);
    return eg.second;
  }
  friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
  friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
  friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
  friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
  friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
  friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }

 private:
  unsigned int _v;
  static internal::barrett bt;
  static unsigned int umod() { return bt.umod(); }
};
template<int id> internal::barrett dynamic_modint<id>::bt(998244353);

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template<class T> using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template<class T> using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template<class> struct is_dynamic_modint : public std::false_type {
};
template<int id> struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {
};

template<class T> using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;


template<typename T> struct Matrix : vector<vector<T>> {
  using vector<vector<T>>::vector;
  using vector<vector<T>>::operator=;
  Matrix() {}
  Matrix(ll N) {
    *this = vector<vector<T>>(N, vector<T>(N, T()));
    for(ll i = 0; i < N; i++) { (*this)[i][i] = 1; }
  }
  Matrix(ll H, ll W, T x = 0) { *this = vector<vector<T>>(H, vector<T>(W, x)); }
  Matrix(vector<vector<T>> v) { *this = v; }
  Matrix operator+(const Matrix &m) const { return Matrix(*this) += m; }
  Matrix operator-(const Matrix &m) const { return Matrix(*this) -= m; }
  Matrix operator*(const Matrix &m) const { return Matrix(*this) *= m; }
  Matrix operator*(const T &x) const { return Matrix(*this) *= x; }
  Matrix operator^(ll n) const { return Matrix(*this) ^= n; }
  Matrix operator+=(const Matrix &m) const {
    ll h = this->size(), w = (*this)[0].size();
    assert(h == m.size() && w == m[0].size());
    for(ll i = 0; i < h; i++) {
      for(ll j = 0; j < w; j++) { *this[i][j] += m[i][j]; }
    }
    return *this;
  }
  Matrix operator-=(const Matrix &m) {
    ll h = this->size(), w = (*this)[0].size();
    assert(h == m.size() && w == m[0].size());
    for(ll i = 0; i < h; i++) {
      for(ll j = 0; j < w; j++) { *this[i][j] -= m[i][j]; }
    }
    return *this;
  }
  Matrix operator*=(const Matrix &m) {
    ll h = this->size(), w = (*this)[0].size();
    assert(w == (ll)m.size());
    vector<vector<T>> r(h, vector<T>(m[0].size(), T(0)));
    for(ll i = 0; i < h; i++) {
      for(ll j = 0; j < (ll)m[0].size(); j++) {
        for(ll k = 0; k < w; k++) { r[i][j] += (*this)[i][k] * m[k][j]; }
      }
    }
    this->swap(r);
    return *this;
  }
  Matrix operator*=(const T &x) {
    ll h = this->size(), w = (*this)[0].size();
    for(ll i = 0; i < h; i++) {
      for(ll j = 0; j < w; j++) { *this[i][j] *= x; }
    }
    return *this;
  }
  Matrix operator^=(ll n) {
    ll h = this->size();
    Matrix m(h);
    while(n) {
      if(n & 1) { m *= *this; }
      *this *= *this;
      n >>= 1LL;
    }
    this->swap(m);
    return *this;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N;
  cin >> N;

  Matrix<mint> A = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}};
  Matrix<mint> B = {{1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}};
  Matrix<mint> dp = {{3}, {1}, {1}, {1}};

  if(N == 1) { cout << 1 << "\n"; }
  if(N == 2) { cout << 1 << "\n"; }
  if(N == 3) { cout << 3 << "\n"; }
  if(N < 4) { return 0; }

  auto C = B * A;

  dp = (C ^ ((N - 3) / 2)) * dp;
  if(~N & 1) { dp = A * dp; }

  cout << dp[0][0].val() << "\n";
}
yukicoder

結果

ソースコード
