#324706 (C++11（廃止可能性あり）) No.801 エレベーター

• 問題: No.801 エレベーター
• ユーザー: ゆゆうた
• 提出日時: 2019-03-17 21:40:51
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,520 bytes
• コンパイル時間: 1,243 ms
• コンパイル使用メモリ: 170,056 KB
• 実行使用メモリ: 220,032 KB
• 最終ジャッジ日時: 2024-07-07 21:19:58
• 合計ジャッジ時間: 11,401 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 10 TLE * 1 -- * 15

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


template<int M, bool IsPrime = false>
class Modulo {
    int n;

    static typename std::enable_if<IsPrime, ll>::type inv(ll a, ll p) {
        return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
    }

public:
    Modulo() : n(0) { ; }

    Modulo(int m) : n(m) {
        if (n >= M)
            n %= M;
        else if (n < 0)
            n = (n % M + M) % M;
    }

    Modulo(ll m) {
        if (m >= M)
            m %= M;
        else if (m < 0)
            m = (m % M + M) % M;
        n = m;
    }

    explicit operator int() const { return n; }

    explicit operator ll() const { return n; }

    bool operator==(const Modulo &a) const { return n == a.n; }

    Modulo &operator+=(const Modulo &a) {
        n += a.n;
        if (n >= M) n -= M;
        return *this;
    }

    Modulo &operator-=(const Modulo &a) {
        n -= a.n;
        if (n < 0) n += M;
        return *this;
    }

    Modulo &operator*=(const Modulo &a) {
        n = (ll(n) * a.n) % M;
        return *this;
    }

    Modulo operator+(const Modulo &a) const {
        Modulo res = *this;
        return res += a;
    }

    Modulo operator-(const Modulo &a) const {
        Modulo res = *this;
        return res -= a;
    }

    Modulo operator-() const { return Modulo(0) - *this; }

    Modulo operator*(const Modulo &a) const {
        Modulo res = *this;
        return res *= a;
    }

    Modulo operator^(ll m) const {
        if (m == 0) return Modulo(1);
        const Modulo a = *this;
        Modulo res = (a * a) ^(m / 2);
        return m % 2 ? res * a : res;
    }

    typename std::enable_if<IsPrime, Modulo>::type
    operator/(const Modulo &a) const {
        return *this * inv(ll(a), M);
    }

    typename std::enable_if<IsPrime, Modulo>::type operator/=(const Modulo &a) {
        return *this *= inv(ll(a), M);
    }

    friend bool is_zero(const Modulo &x) { return int(x) == 0; }

    friend int abs(const Modulo &x) { return int(x); }

    static Modulo fact(int n, bool sw = true) {
        static std::vector<Modulo> v1 = {1}, v2 = {1};
        if (n >= (int) v1.size()) {
            const int from = v1.size(), to = n + 1024;
            v1.reserve(to);
            v2.reserve(to);
            for (int i = from; i < to; ++i) {
                v1.push_back(v1.back() * Modulo<M, true>(i));
                v2.push_back(v2.back() / Modulo<M, true>(i));
            }
        }
        return sw ? v1[n] : v2[n];
    }

    static Modulo comb(int a, int b) {
        if (b < 0 || b > a) return 0;
        return Modulo::fact(a, true) * Modulo::fact(b, false) *
               Modulo::fact(a - b, false);
    }
};

typedef Modulo<1000000007, true> mInt;


template<typename T>
class Vec {
protected:
    using iterator = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    using reference = T &;
    using const_reference = const T &;
    std::vector<T> v;

    template<typename Unop>
    Vec<T> unop_new(Unop op) const {
        Vec<T> res(v.size());
        transform(begin(v), end(v), res.begin(), op);
        return res;
    }

    template<typename Binop>
    Vec<T> &binop(const Vec<T> &r, Binop op) {
        transform(r.begin(), r.end(), v.begin(), v.begin(), op);
        return *this;
    }

    template<typename Binop>
    Vec<T> binop_new(const Vec<T> &r, Binop op) const {
        Vec<T> res(v.size());
        transform(r.begin(), r.end(), v.begin(), res.begin(), op);
        return res;
    }

public:
    Vec(int n) : v(n) {}

    Vec(int n, const T &val) : v(n, val) {}

    Vec(const std::vector<T> &w) : v(w) {}

    int size() const noexcept { return v.size(); }

    const_iterator begin() const noexcept { return v.begin(); }

    const_iterator end() const noexcept { return v.end(); }

    iterator begin() noexcept { return v.begin(); }

    iterator end() noexcept { return v.end(); }

    reference operator[](int i) { return v[i]; }

    const_reference operator[](int i) const { return v[i]; }

    Vec<T> operator-() const {
        return unop_new([](T val) { return -val; });
    };

    Vec<T> &operator+=(const Vec<T> &r) {
        return binop(r, [](T x, T y) { return x + y; });
    }

    Vec<T> &operator-=(const Vec<T> &r) {
        return binop(r, [](T x, T y) { return x - y; });
    }

    Vec<T> operator+(const Vec<T> &r) const {
        return binop_new(r, [](T x, T y) { return x + y; });
    }

    Vec<T> operator-(const Vec<T> &r) const {
        return binop_new(r, [](T x, T y) { return x - y; });
    }

    T dot(const Vec<T> &r) const {
        return inner_product(v.begin(), v.end(), r.begin(), T(0));
    }

    T norm() const { return this->dot(v); }

    void push_back(const T &r) { v.push_back(r); }

    void concat(const Vec<T> &r) { v.insert(v.end(), r.begin(), r.end()); }
};

template<typename T>
class Matrix : public Vec<Vec<T>> {
public:
    using Vec<Vec<T>>::Vec;

    Matrix(int n, int m, const T &val) : Vec<Vec<T>>::Vec(n, Vec<T>(m, val)) {}

    int Y() const { return this->size(); }

    int X() const { return (*this)[0].size(); }

    Matrix<T> transpose() const {
        const int row = Y(), col = X();
        Matrix res(col, row);
        for (int j = 0; j < col; ++j) {
            for (int i = 0; i < row; ++i) {
                res[j][i] = (*this)[i][j];
            }
        }
        return res;
    }

    Matrix<T> operator*(const Matrix<T> &r) const {
        Matrix<T> tr = r.transpose();
        const int row = Y(), col = tr.Y();
        assert(X() == tr.X());
        Matrix<T> res(row, col);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                res[i][j] = (*this)[i].dot(tr[j]);
            }
        }
        return res;
    }

    Vec<T> operator*(const Vec<T> &r) const {
        const int row = Y(), col = r.Y();
        assert(r.size() == col);
        Vec<T> res(row);
        for (int i = 0; i < row; ++i) {
            res[i] = (*this)[i].dot(r);
        }
        return res;
    }

    Matrix<T> &operator*=(const Matrix<T> &r) { return *this = *this * r; }

    Matrix<T> operator^(ll n) const {
        const int m = Y();
        assert(m == X());
        Matrix<T> A = *this, res(m, m, 0);
        for (int i = 0; i < m; ++i) res[i][i] = 1;
        while (n > 0) {
            if (n % 2) res *= A;
            A = A * A;
            n /= 2;
        }
        return res;
    }

    void concat_right(const Vec<T> &r) {
        const int n = Y();
        assert(n == r.size());
        for (int i = 0; i < n; ++i) {
            (*this)[i].push_back(r[i]);
        }
    }

    void concat_right(const Matrix<T> &r) {
        const int n = Y();
        assert(n == r.Y());
        for (int i = 0; i < n; ++i) {
            (*this)[i].concat(r[i]);
        }
    }

    void concat_below(const Vec<T> &r) {
        assert(Y() == 0 || X() == r.size());
        this->push_back(r);
    }

    void concat_below(const Matrix<T> &r) {
        assert(Y() == 0 || X() == r.X());
        for (Vec<T> i : r) (*this).push_back(i);
    }

    int rank() const {
        Matrix<T> A = *this;
        if (Y() == 0) return 0;
        const int n = Y(), m = X();
        int r = 0;
        for (int i = 0; r < n && i < m; ++i) {
            int pivot = r;
            for (int j = r + 1; j < n; ++j) {
                if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
            }
            std::swap(A[pivot], A[r]);
            if (is_zero(A[r][i])) continue;
            for (int k = m - 1; k >= i; --k) A[r][k] = A[r][k] / A[r][i];
            for (int j = r + 1; j < n; ++j) {
                for (int k = m - 1; k >= i; --k) {
                    A[j][k] -= A[r][k] * A[j][i];
                }
            }
            ++r;
        }
        return r;
    }

    T det() const {
        const int n = Y();
        if (n == 0) return 1;
        assert(Y() == X());
        Matrix<T> A = *this;
        T D = 1;
        for (int i = 0; i < n; ++i) {
            int pivot = i;
            for (int j = i + 1; j < n; ++j) {
                if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
            }
            std::swap(A[pivot], A[i]);
            D = D * A[i][i] * T(i != pivot ? -1 : 1);
            if (is_zero(A[i][i])) break;
            for (int j = i + 1; j < n; ++j) {
                for (int k = n - 1; k >= i; --k) {
                    A[j][k] -= A[i][k] * A[j][i] / A[i][i];
                }
            }
        }
        return D;
    }
};

mInt fib(ll n) {
    Matrix<mInt> m(2, 2);
    m[0][1] = 1;
    m[1][1] = 1;
    m[1][0] = 1;
    auto M = (m ^ (n - 1));
    return M[0][0] + M[0][1];
}


mInt imos[3010][3010];

pair<int, int> seg[3010];

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        seg[i] = {a, b};
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i >= seg[j].first && i < seg[j].second) {
                imos[i][seg[j].first] += 1;
                imos[i][seg[j].second] -= 1;
            }
        }
        for (int j = 1; j < N; j++) {
            imos[i][j] += imos[i][j - 1];
        }
    }

    Matrix<mInt> mat(N, N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            mat[i][j] = imos[i][j];
        }
    }

    auto X = (mat ^ K);


    cout << (ll) X[0][N-1] << endl;

    return 0;
}