結果

問題 No.801 エレベーター
ユーザー ntudantuda
提出日時 2021-10-30 14:01:06
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,164 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 230,784 KB
最終ジャッジ日時 2024-04-16 16:20:59
合計ジャッジ時間 17,927 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 542 ms
49,640 KB
testcase_01 AC 521 ms
44,416 KB
testcase_02 AC 519 ms
44,296 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

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