結果

問題 No.801 エレベーター
ユーザー SuikabaSuikaba
提出日時 2019-03-17 21:50:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 2,671 bytes
コンパイル時間 1,828 ms
コンパイル使用メモリ 204,820 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 21:47:55
合計ジャッジ時間 4,639 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 129 ms
5,376 KB
testcase_14 AC 133 ms
5,376 KB
testcase_15 AC 133 ms
5,376 KB
testcase_16 AC 135 ms
5,376 KB
testcase_17 AC 129 ms
5,376 KB
testcase_18 AC 132 ms
5,376 KB
testcase_19 AC 131 ms
5,376 KB
testcase_20 AC 133 ms
5,376 KB
testcase_21 AC 131 ms
5,376 KB
testcase_22 AC 128 ms
5,376 KB
testcase_23 AC 129 ms
5,376 KB
testcase_24 AC 130 ms
5,376 KB
testcase_25 AC 132 ms
5,376 KB
testcase_26 AC 129 ms
5,376 KB
testcase_27 AC 128 ms
5,376 KB
testcase_28 AC 60 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <int Mod, bool IsPrime = false>
class mod_int {
    using ll = long long;

public:
    constexpr mod_int() : n(0) {}
    constexpr mod_int(int n_) : n(n_) {
        if(n >= Mod)     n %= Mod;
        else if(n < 0) n = (n % Mod + Mod) % Mod;
    }
    constexpr mod_int(ll n_) : n(n_) { n = (n + Mod) % Mod; }

    constexpr operator int() const { return n; }
    constexpr operator ll() const  { return n; }

    constexpr bool operator==(mod_int const& other) const { return n == other.n; }
    constexpr mod_int& operator+=(mod_int const& other) {
        if((n += other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator-=(mod_int const& other) {
        if((n += Mod - other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator*=(mod_int const& other) {
        n = (unsigned long long)n * other.n % Mod;
        return *this;
    }
    constexpr typename std::enable_if<IsPrime, mod_int>::type& operator/=(mod_int const& other) {
        return *this *= other.inverse();
    }
    constexpr mod_int operator+(mod_int other) const { return mod_int(*this) += other; }
    constexpr mod_int operator-(mod_int other) const { return mod_int(*this) -= other; }
    constexpr mod_int operator*(mod_int other) const { return mod_int(*this) *= other; }
    constexpr mod_int operator/(mod_int other) const { return mod_int(*this) /= other; }

    constexpr typename std::enable_if<IsPrime, mod_int>::type inverse() const {
        ll a = n, b = Mod, u = 1, v = 0;
        while(b) {
            ll t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        return mod_int(u);
    }

private:
    ll n;
};

template <int Mod, bool IsPrime>
std::ostream& operator<<(std::ostream& os, mod_int<Mod, IsPrime> const& n) {
    os << (int)n;
    return os;
}

constexpr int default_mod = 1000000007;

using mint = mod_int<default_mod, true>; // default


int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> l(m), r(m);
    for(int i = 0; i < m; ++i) {
        cin >> l[i] >> r[i];
        l[i]--;
    }

    vector<mint> dp(n + 1);
    dp[0] = 1;
    for(int lp = 0; lp < k; ++lp) {
        vector<mint> sum(n + 1), ndp(n + 1);
        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + dp[i];
        }
        for(int i = 0; i < m; ++i) {
            ndp[l[i]] += sum[r[i]] - sum[l[i]];
            ndp[r[i]] -= sum[r[i]] - sum[l[i]];
        }
        for(int i = 0; i < n; ++i) {
            ndp[i + 1] += ndp[i];
        }
        dp = move(ndp);
    }
    cout << dp[n - 1] << endl;
}
0