結果
問題 | No.1172 Add Recursive Sequence |
ユーザー |
![]() |
提出日時 | 2020-08-14 23:10:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,601 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 61,100 KB |
最終ジャッジ日時 | 2024-10-10 16:37:24 |
合計ジャッジ時間 | 11,909 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 TLE * 1 -- * 1 |
ソースコード
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 Kitamasa(C, X, k, e0=0, e1=1, mod=10**9+7): ''' 0-indexed calc X[k] ''' n = len(X) def _plus1(g): ret = [(g[i-1] + g[-1] * C[i]) % mod for i in range(n)] ret[0] = g[-1] * C[0] % mod return ret def _mult2(g): ret = [e0]*(2 * n - 1) for i in range(n): for j in range(n): ret[i + j] = (ret[i + j] + g[i] * g[j]) % mod for i in range(2*n-2, n-1, -1): for j in range(n): ret[i + j - n] = (ret[i + j - n] + ret[i] * C[j]) % mod return ret[:n] g = [e0]*n g[0] = e1 t = k.bit_length() for i in range(t-1, -1, -1): g = _mult2(g) if k & (1<<i): g = _plus1(g) ans = e0 for i in range(n): ans = (ans + g[i] * X[i]) % mod return ans def solve(): k, n, m = nm() a = nl() c = nl()[::-1] f = [0]*n g = [list() for _ in range(n+1)] d = dict() mod = 10**9 + 7 for _ in range(m): l, r = nm() f[l] += 1 g[r].append(r-l) 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 def mult2(g): ret = [0]*(2 * k - 1) for i in range(k): for j in range(k): ret[i + j] = (ret[i + j] + g[i] * g[j]) % mod for i in range(2 * k - 2, k - 1, -1): for j in range(k): ret[i + j - k] = (ret[i + j - k] + ret[i] * c[j]) % mod return ret[:k] def search(x): g = [x] while g[-1] >= k and g[-1] not in d: v = g[-1] g.append(v ^ 1 if v & 1 else v >> 1) while g: v = g.pop() if v in d: continue if v < k: ret = [0] * k ret[v] = 1 d[v] = ret elif v & 1: d[v] = plus1(d[v-1]) else: d[v] = mult2(d[v>>1]) return d[x] 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 = search(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()