結果

問題 No.801 エレベーター
ユーザー minami
提出日時 2019-03-18 00:49:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 3,275 bytes
コンパイル時間 1,670 ms
コンパイル使用メモリ 175,140 KB
実行使用メモリ 38,528 KB
最終ジャッジ日時 2024-07-08 07:50:13
合計ジャッジ時間 4,180 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif
//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1'000'000'007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
template<int MOD>
struct ModInt {
    static const int kMod = MOD;
    unsigned x;
    ModInt() : x(0) {}
    ModInt(signed sig) { int sigt = sig % kMod; if (sigt < 0) sigt += kMod; x = sigt; }
    ModInt(signed long long sig) { int sigt = sig % kMod; if (sigt < 0) sigt += kMod; x = sigt; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= kMod) x -= kMod; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += kMod - that.x) >= kMod) x -= kMod; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % kMod; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const {
        signed a = x, b = kMod, u = 1, v = 0;
        while (b) {
            signed t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += kMod;
        ModInt res; res.x = (unsigned)u;
        return res;
    }
};
template<int MOD>
ostream &operator << (ostream &os, const ModInt<MOD> &m) { return os << m.x; }
template<int MOD>
istream &operator >> (istream &is, ModInt<MOD> &m) { signed long long s; is >> s; m = ModInt<MOD>(s); return is; };
using mint = ModInt<1000000007>;
mint pow(mint a, unsigned long long k) {
    mint r = 1;
    while (k) {
        if (k & 1) r *= a;
        a *= a;
        k >>= 1;
    }
    return r;
}
vector<mint> fact, factinv;
void precomputeFactorial(int N) {
    N = min(N, mint::kMod - 1);
    fact.resize(N + 1); factinv.resize(N + 1);
    fact[0] = 1;
    rep(i, 1, N + 1) fact[i] = fact[i - 1] * i;
    factinv[N] = fact[N].inverse();
    for (int i = N; i >= 1; i--) factinv[i - 1] = factinv[i] * i;
}
mint combi(int n, int r) {
    if (n >= mint::kMod)
        return combi(n % mint::kMod, r % mint::kMod) * combi(n / mint::kMod, r / mint::kMod);
    return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r];
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, K; cin >> N >> M >> K;
    vector<int> L(M), R(M); rep(i, 0, M) {
        cin >> L[i] >> R[i];
        L[i], R[i];
        L[i]--;
    }
    vector<vector<mint>> dp(K + 1, vector<mint>(N));
    dp[0][0] = 1;
    rep(k, 0, K) {
        vector<mint> sum(N + 1);
        rep(i, 0, N) {
            sum[i + 1] += sum[i] + dp[k][i];
        }
        vector<mint> imos(N + 1);
        rep(i, 0, M) {
            mint add = sum[R[i]] - sum[L[i]];
            imos[L[i]] += add;
            imos[R[i]] -= add;
        }
        rep(i, 0, N) {
            imos[i + 1] += imos[i];
        }
        rep(i, 0, N) {
            dp[k + 1][i] = imos[i];
        }
    }
    cout << dp[K][N - 1] << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0