結果

問題 No.1172 Add Recursive Sequence
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-08-14 22:46:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 654 ms / 4,000 ms
コード長 1,118 bytes
コンパイル時間 846 ms
コンパイル使用メモリ 87,200 KB
実行使用メモリ 93,292 KB
最終ジャッジ日時 2023-07-31 23:22:55
合計ジャッジ時間 4,620 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,420 KB
testcase_01 AC 72 ms
71,100 KB
testcase_02 AC 71 ms
71,576 KB
testcase_03 AC 70 ms
71,152 KB
testcase_04 AC 69 ms
71,488 KB
testcase_05 AC 71 ms
71,204 KB
testcase_06 AC 111 ms
78,136 KB
testcase_07 AC 113 ms
78,096 KB
testcase_08 AC 93 ms
77,000 KB
testcase_09 AC 93 ms
77,272 KB
testcase_10 AC 136 ms
80,368 KB
testcase_11 AC 132 ms
79,700 KB
testcase_12 AC 112 ms
78,832 KB
testcase_13 AC 109 ms
78,720 KB
testcase_14 AC 251 ms
92,884 KB
testcase_15 AC 203 ms
88,916 KB
testcase_16 AC 654 ms
93,292 KB
testcase_17 AC 507 ms
89,140 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

aの計算自体は行列累乗で可能そう

クエリを毎回処理するのは無理
→imosで処理？

線形だから可能？
行列を計算しつついもす法をやる

aをNまで計算しておく
lで入るときに加え、rで抜けるときに引く

"""

from sys import stdin

K,N,M = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))
mod = 10**9+7

for i in range(K+1,N+K+1):

    now = 0
    for j in range(K):
        now += a[-1-j] * c[j]
        now %= mod
    a.append(now)

l = [0] * (N)
r = [ [] for i in range(N)]

for i in range(M):
    L,R = map(int,stdin.readline().split())
    l[L] += 1
    r[R-1].append(R-L-1)

lis = [0] * K
for i in range(N):

    #plus
    if l[i] > 0:
        for j in range(K):
            lis[i+j] += a[j] * l[i]
            lis[i+j] %= mod
    print (lis[i] % mod)
    for t in r[i]:
        for j in range(K):
            lis[i+j] -= a[t+j]
            lis[i+j] %= mod

    now = 0
    for j in range(K):
        now += lis[-1-j] * c[j]
        now %= mod
    lis.append(now)
0