結果

問題 No.1172 Add Recursive Sequence
ユーザー Salmonize
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0