結果

問題 No.801 エレベーター
コンテスト
ユーザー 梧桐
提出日時 2026-04-17 21:11:43
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,528 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 666 ms
コンパイル使用メモリ 76,780 KB
実行使用メモリ 537,984 KB
最終ジャッジ日時 2026-04-17 21:12:40
合計ジャッジ時間 17,449 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 10 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 3010, MOD = 1000000007;

int n, m, k, diff[N][N];

struct Matrix {
    int v[N][N];
    Matrix operator*(Matrix o) {
        Matrix ret = {};
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int l = 1; l <= n; ++l) {
                    ret.v[i][l] = (ret.v[i][l] + 1LL * v[i][j] * o.v[j][l]) % MOD;
                }
            }
        }
        return ret;
    }
    Matrix operator*=(Matrix o) {
        *this = *this * o;
        return *this;
    }
};
Matrix a;

Matrix QMI(Matrix base, int p) {
    Matrix ret = {};
    for (int i = 1; i <= n; ++i) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret *= base;
        base *= base;
        p >>= 1;
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        diff[l][l]++;
        diff[l][r + 1]--;
        diff[r + 1][l]--;
        diff[r + 1][r + 1]++;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            diff[i][j] += diff[i][j - 1];
        }
    }
    for (int j = 1; j <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            a.v[i][j] = diff[i][j];
        }
    }

    a = QMI(a, k);
    printf("%d\n", a.v[n][1]);

    return 0;
}
0