結果

問題 No.801 エレベーター
コンテスト
ユーザー kakira9618
提出日時 2019-03-17 23:05:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,563 bytes
コンパイル時間 1,744 ms
コンパイル使用メモリ 169,580 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-07-08 01:50:44
合計ジャッジ時間 5,211 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

// これTLEじゃん（）

#include <bits/stdc++.h>

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

const int mod = 1e9 + 7;

vector<vector<ll>> mul(vector<vector<ll>> &A, vector<vector<ll>> &B, int mod) {
    int N = A.size(), M = B[0].size(), K = A[0].size();
    vector<vector<ll>> ret(N, vector<ll>(M));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < K; k++) {
                ret[i][j] += A[i][k] * B[k][j];
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

vector<vector<ll>> pow(vector<vector<ll>> &A, int n, int mod) {
    if (n == 0) {
        int N = A.size();
        vector<vector<ll>> E(N, vector<ll>(N));
        for(int i = 0; i < N; i++) {
            E[i][i] = 1;
        }
        return E;
    }
    vector<vector<ll>> m = pow(A, n / 2, mod);
    if (n % 2 == 1) {
        vector<vector<ll>> temp = mul(m, m, mod);
        return mul(A, temp, mod);
    } else {
        return mul(m, m, mod);
    }
}

void solve() {
    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];
    }
    
    vector<vector<ll>> C;
    for(int p = 0; p <= N; p++) {
        vector<ll> c(N + 1);
        vector<int> imos(N + 2);
        for(int i = 0; i < M; i++) {
            int l = L[i], r = R[i];
            if (l <= p && p <= r) {
                imos[l]++;
                imos[r + 1]--;
            }
        }
        int now = 0;
        for(int j = 0; j <= N; j++) {
            now += imos[j];
            c[j] = now;
        }
        C.push_back(c);
    }
    vector<vector<ll>> C_ = pow(C, K, mod);
    vector<vector<ll>> v(N + 1, vector<ll>(1, 0));
    v[1][0] = 1;
    vector<vector<ll>> ret = mul(C_, v, mod);
    cout << ret[N][0] << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}
0