結果

問題 No.1172 Add Recursive Sequence
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2020-08-14 22:46:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 559 ms / 4,000 ms
コード長 1,118 bytes
コンパイル時間 458 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 91,680 KB
最終ジャッジ日時 2024-10-10 16:09:28
合計ジャッジ時間 3,826 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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