結果
問題 | No.1172 Add Recursive Sequence |
ユーザー | Salmonize |
提出日時 | 2020-08-14 23:16:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,386 ms / 4,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 378,032 KB |
最終ジャッジ日時 | 2024-10-10 16:40:01 |
合計ジャッジ時間 | 7,970 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 |
ソースコード
import sys readline = sys.stdin.buffer.readline readall = sys.stdin.read ns = lambda: readline().rstrip() ni = lambda: int(readline().rstrip()) nm = lambda: map(int, readline().split()) nl = lambda: list(map(int, readline().split())) prn = lambda x: print(*x, sep='\n') def solve(): mod = 10**9 + 7 k, n, m = nm() a = nl() c = nl()[::-1] def plus1(g): ret = [(g[i-1] + g[-1] * c[i]) % mod for i in range(k)] ret[0] = g[-1] * c[0] % mod return ret f = [0]*n g = [list() for _ in range(n+1)] d = [[0]*k for _ in range(n)] d[0][0] = 1 for i in range(n-1): d[i+1] = plus1(d[i]) for _ in range(m): l, r = nm() f[l] += 1 g[r].append(r-l) cur = [0] * k for i in range(n): # print(i, f[i], g[i]) cur = plus1(cur) cur[0] += f[i] for x in g[i]: neg = d[x] for j in range(k): cur[j] -= neg[j] # print(cur, i, f[i], g[i]) print(sum(cur[j]*a[j] for j in range(k)) % mod) # cur = [1, 0] # for i in range(10): # cur = plus1(cur) # print(cur, search(i+1)) return solve()