結果
問題 | No.1172 Add Recursive Sequence |
ユーザー | Salmonize |
提出日時 | 2020-08-14 23:16:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,550 ms / 4,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 377,848 KB |
最終ジャッジ日時 | 2024-04-18 23:06:47 |
合計ジャッジ時間 | 8,500 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
52,736 KB |
testcase_01 | AC | 43 ms
52,608 KB |
testcase_02 | AC | 44 ms
52,352 KB |
testcase_03 | AC | 47 ms
52,224 KB |
testcase_04 | AC | 47 ms
52,224 KB |
testcase_05 | AC | 46 ms
51,968 KB |
testcase_06 | AC | 110 ms
77,100 KB |
testcase_07 | AC | 108 ms
77,184 KB |
testcase_08 | AC | 113 ms
77,312 KB |
testcase_09 | AC | 124 ms
77,256 KB |
testcase_10 | AC | 172 ms
82,816 KB |
testcase_11 | AC | 163 ms
83,436 KB |
testcase_12 | AC | 135 ms
81,916 KB |
testcase_13 | AC | 149 ms
81,004 KB |
testcase_14 | AC | 479 ms
115,356 KB |
testcase_15 | AC | 347 ms
113,204 KB |
testcase_16 | AC | 2,550 ms
377,848 KB |
testcase_17 | AC | 2,407 ms
377,532 KB |
ソースコード
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()