結果
問題 |
No.1879 How many matchings?
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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"; }