結果

問題 No.801 エレベーター
ユーザー ntuda
提出日時 2021-10-30 14:01:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,164 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 242,176 KB
最終ジャッジ日時 2024-10-07 13:39:58
合計ジャッジ時間 15,936 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 10 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M,K = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(M)]
MOD = 10 ** 9 + 7

Mat = [[0]*(N+1) for _ in range(N+1)]
Mat2 = [[0]*(N) for _ in range(N)]

#2次元いもす

for l, r in LR:
    Mat[l-1][l-1] += 1
    Mat[l-1][r] -= 1
    Mat[r][l-1] -= 1
    Mat[r][r] += 1

for i in range(N):
    for j in range(N):
        if i == 0:
            if j == 0:
                Mat2[i][j] = Mat[i][j]
            else:
                Mat2[i][j] = Mat2[i][j-1] + Mat[i][j]
        else:
            if j == 0:
                Mat2[i][j] = Mat2[i-1][j] + Mat[i][j]
            else:
                Mat2[i][j] = - Mat2[i-1][j-1] + Mat2[i-1][j] + Mat2[i][j-1] + Mat[i][j]
#print(Mat2)

import numpy as np
A = np.array(Mat2,dtype = np.int64)
n = K.bit_length()
B = np.eye(N)
C = np.array([1] + [0] * (N-1),dtype= np.int64).T
M = np.array([[MOD] * N for _ in range(N)])
AA = [[] for _ in range(n)]
AA[0] = A
for i in range(1,n):
    tmp = np.dot(AA[i-1],AA[i-1])
    AA[i] = np.mod(tmp,M)
i = 0
while K > 0:
    if K % 2 == 1:
        B = np.dot(B,AA[i])
        B = np.mod(B,M)
    K //= 2
    i += 1
D = np.dot(B,C)
print(int(D[N-1]) % MOD)
0