結果
| 問題 | No.1331 Moving Penguin |
| ユーザー |
 KoD
|
| 提出日時 | 2021-01-08 21:37:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 457 ms / 1,500 ms |
| コード長 | 6,881 bytes |
| コンパイル時間 | 1,008 ms |
| コンパイル使用メモリ | 80,024 KB |
| 最終ジャッジ日時 | 2025-01-17 11:25:39 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 49 |
ソースコード
#line 1 "main.cpp"/*** @title Template*/#include <iostream>#include <algorithm>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"class range {struct iter {std::size_t itr;constexpr iter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { ++itr; }constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};struct reviter {std::size_t itr;constexpr reviter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { --itr; }constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};const iter first, last;public:constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }constexpr iter begin() const noexcept { return first; }constexpr iter end() const noexcept { return last; }constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }constexpr reviter rend() const noexcept { return reviter(*first - 1); }};/*** @title Range*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#include <cstdint>constexpr std::pair<int64_t, int64_t> mod_inv(int64_t a, int64_t b) {if ((a %= b) == 0) return { b, 0 };int64_t s = b, t = (a < 0 ? a + b : a);int64_t m0 = 0, m1 = 1, tmp = 0;while (t > 0) {const auto u = s / t;s -= t * u; m0 -= m1 * u;tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp;}return { s, (m0 < 0 ? m0 + b / s : m0) };}/*** @title Extended GCD*/#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#include <type_traits>template <class Modulus>class modular {public:using value_type = uint32_t;using cover_type = uint64_t;static constexpr uint32_t mod() { return Modulus::mod(); }template <class T>static constexpr value_type normalize(T value_) noexcept {if (value_ < 0) {value_ = -value_;value_ %= mod();if (value_ == 0) return 0;return mod() - value_;}return value_ % mod();}private:value_type value;template <bool IsPrime, std::enable_if_t<IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept { return power(*this, mod() - 2); }template <bool IsPrime, std::enable_if_t<!IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept {const auto tmp = mod_inv(value, mod());assert(tmp.first == 1);return modular(tmp.second);}public:constexpr modular() noexcept : value(0) { }template <class T>explicit constexpr modular(T value_) noexcept : value(normalize(value_)) { }template <class T>explicit constexpr operator T() const noexcept { return static_cast<T>(value); }constexpr value_type get() const noexcept { return value; }constexpr value_type &extract() noexcept { return value; }constexpr modular operator - () const noexcept { return modular(mod() - value); }constexpr modular operator ~ () const noexcept { return inverse(*this); }constexpr modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }constexpr modular& operator += (const modular &rhs) noexcept {if ((value += rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }constexpr modular& operator -= (const modular &rhs) noexcept {if ((value += mod() - rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }constexpr modular& operator *= (const modular &rhs) noexcept {value = (cover_type) value * rhs.value % mod();return *this;}constexpr modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }constexpr modular& operator /= (const modular &rhs) noexcept { return (*this) *= inverse(rhs); }constexpr bool zero() const noexcept { return value == 0; }constexpr bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }constexpr bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }friend constexpr modular inverse(const modular &val) noexcept { return val.inverse_helper<Modulus::is_prime>(); }friend constexpr modular power(modular val, cover_type exp) noexcept {modular res(1);for (; exp > 0; exp >>= 1, val *= val) if (exp & 1) res *= val;return res;}};template <uint32_t Mod, bool IsPrime = true>struct static_modulus {static constexpr uint32_t mod() noexcept { return Mod; }static constexpr bool is_prime = IsPrime;};template <uint32_t Id = 0, bool IsPrime = false>struct dynamic_modulus {static uint32_t &mod() noexcept { static uint32_t val = 0; return val; }static constexpr bool is_prime = IsPrime;};template <uint32_t Mod, bool IsPrime = true>using mint32_t = modular<static_modulus<Mod, IsPrime>>;using rmint32_t = modular<dynamic_modulus<>>;/** @title Modint*/#line 16 "main.cpp"using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr i32 inf32 = (u32) ~0 >> 2;constexpr i64 inf64 = (u64) ~0 >> 2;template <class T>using Vec = std::vector<T>;using Fp = mint32_t<1000000007>;int main() {usize N;std::cin >> N;Vec<usize> A(N);for (auto &x: A) {std::cin >> x;}Vec<std::array<Fp, 300>> add(N);Vec<Fp> dp(N);dp[0] = Fp(1);for (auto i: range(0, N - 1)) {if (A[i] >= 300) {for (usize j = i + A[i]; j < N; j += A[i]) {dp[j] += dp[i];}}else {const auto j = i + A[i];if (j < N) {dp[j] += dp[i];add[j][A[i]] += dp[i];}}if (A[i] != 1) {dp[i + 1] += dp[i];}for (auto k: range(0, 300)) {const auto j = i + k;if (j < N) {dp[j] += add[i][k];add[j][k] += add[i][k];}}}std::cout << dp[N - 1] << '\n';return 0;}