結果
| 問題 | No.801 エレベーター |
| ユーザー |
 noshi91
|
| 提出日時 | 2019-03-17 21:43:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 73 ms / 2,000 ms |
| コード長 | 6,355 bytes |
| コンパイル時間 | 726 ms |
| コンパイル使用メモリ | 75,588 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-07 21:28:40 |
| 合計ジャッジ時間 | 2,786 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
//#define NDEBUG#include <cstddef>#include <cstdint>#include <vector>namespace n91 {using i8 = std::int_least8_t;using i32 = std::int_least32_t;using i64 = std::int_least64_t;using u8 = std::uint_least8_t;using u32 = std::uint_least32_t;using u64 = std::uint_least64_t;using isize = std::ptrdiff_t;using usize = std::size_t;class rep {const usize f, l;public:class itr {friend rep;usize i;constexpr itr(const usize x) noexcept : i(x) {}public:void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr rep(const usize first, const usize last) noexcept: f(first), l(last) {}constexpr itr begin() const noexcept { return itr(f); }constexpr itr end() const noexcept { return itr(l); }};class revrep {const usize f, l;public:class itr {friend revrep;usize i;constexpr itr(usize x) noexcept : i(x) {}public:void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}constexpr itr begin() const noexcept { return itr(l); }constexpr itr end() const noexcept { return itr(f); }};template <class T> using vec_alias = std::vector<T>;template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) {return a < b ? b - a : a - b;}} // namespace n91#include <cassert>#include <cstdint>namespace n91 {template <std::uint_least32_t Modulus> class modint {using u32 = std::uint_least32_t;using u64 = std::uint_least64_t;using i64 = std::int_fast64_t;class optimize_tag_t {};static constexpr optimize_tag_t optimize_tag{};public:using value_type = u32;value_type a;private:static constexpr value_type cst(i64 x) noexcept {x %= static_cast<i64>(Modulus);if (x < static_cast<i64>(0)) {x += static_cast<i64>(Modulus);}return static_cast<value_type>(x);}constexpr modint(optimize_tag_t, const value_type &x) noexcept : a(x) {}public:constexpr modint() noexcept : a(static_cast<value_type>(0)) {}constexpr modint(const i64 &x) noexcept : a(cst(x)) {}constexpr value_type value() const noexcept { return a; }constexpr modint operator+(const modint &o) const noexcept {return modint(optimize_tag,a + o.a < Modulus ? a + o.a : a + o.a - Modulus);}constexpr modint operator-(const modint &o) const noexcept {return modint(optimize_tag, a < o.a ? a + Modulus - o.a : a - o.a);}constexpr modint operator*(const modint &o) const noexcept {return modint(optimize_tag,static_cast<value_type>(static_cast<u64>(a) * static_cast<u64>(o.a) %static_cast<u64>(Modulus)));}constexpr modint operator/(const modint &o) const {return modint(optimize_tag,static_cast<value_type>(static_cast<u64>(a) * static_cast<u64>((~o).a) %static_cast<u64>(Modulus)));}modint &operator+=(const modint &o) noexcept {if ((a += o.a) >= Modulus)a -= Modulus;return *this;}modint &operator-=(const modint &o) noexcept {if (a < o.a)a += Modulus;a -= o.a;return *this;}modint &operator*=(const modint &o) noexcept {a = static_cast<value_type>(static_cast<u64>(a) * static_cast<u64>(o.a) %static_cast<u64>(Modulus));return *this;}modint &operator/=(const modint &o) {a = static_cast<u64>(a) * (~o).a % Modulus;return *this;}constexpr modint inverse() const noexcept {assert(a != static_cast<value_type>(0) && "0 does not have inverse");return pow(static_cast<u64>(Modulus - static_cast<value_type>(2)));}constexpr modint operator~() const noexcept { return inverse(); }constexpr modint operator-() const noexcept {if (a == static_cast<value_type>(0)) {return modint(optimize_tag, static_cast<value_type>(0));}else {return modint(optimize_tag, Modulus - a);}}modint &operator++() noexcept {if (++a == Modulus) {a = static_cast<value_type>(0);}return *this;}modint &operator--() noexcept {if (a == static_cast<value_type>(0)) {a = Modulus;}--a;return *this;}constexpr bool operator==(const modint &o) const noexcept { return a == o.a; }constexpr bool operator!=(const modint &o) const noexcept { return a != o.a; }constexpr bool operator<(const modint &o) const noexcept { return a < o.a; }constexpr bool operator<=(const modint &o) const noexcept { return a <= o.a; }constexpr bool operator>(const modint &o) const noexcept { return a > o.a; }constexpr bool operator>=(const modint &o) const noexcept { return a >= o.a; }constexpr explicit operator bool() const noexcept { return a; }constexpr explicit operator value_type() const noexcept { return a; }modint pow(u64 x) const noexcept {u64 t = a, u = 1;while (x) {if (x & 1)u = u * t % Modulus;t = (t * t) % Modulus;x >>= 1;}return modint(optimize_tag, static_cast<value_type>(u));}};} // namespace n91#include <algorithm>#include <iostream>#include <utility>#include <array>namespace n91 {void main_() {using mint = modint<1000000007>;usize n, m, k;std::cin >> n >> m >> k;struct el {usize l, r;};std::vector<el> els(m);for (auto &e : els) {std::cin >> e.l >> e.r;--e.l;}std::vector<mint> dp(n + 1), prev(n + 1), sum(n + 1);dp[0] = 1;for (const auto k_cnt : rep(0, k)) {std::swap(dp, prev);std::fill(dp.begin(), dp.end(), mint(0));sum[0] = 0;for (const auto i : rep(0, n)) {sum[i + 1] = sum[i] + prev[i];}for (const auto &e : els) {const mint s = sum[e.r] - sum[e.l];dp[e.l] += s;dp[e.r] -= s;}for (const auto i : rep(0, n)) {dp[i + 1] += dp[i];}}std::cout << dp[n - 1].a << std::endl;}} // namespace n91int main() {n91::main_();return 0;}