結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
|
提出日時 | 2025-01-19 01:04:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,562 bytes |
コンパイル時間 | 915 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 122,828 KB |
最終ジャッジ日時 | 2025-01-19 01:04:35 |
合計ジャッジ時間 | 6,411 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 WA * 16 |
ソースコード
N, Q = map(int, input().split())A = list(map(int, input().split()))R = list(map(int, input().split()))def primitive_root(m):"""整数mの最小原始根を計算するParameters----------m : int2以上の整数Returns-------intmの最小原始根"""if m == 2:return 1if m == 167772161:return 3if m == 469762049:return 3if m == 754974721:return 11if m == 998244353:return 3if m == 1000000007:return 5divs = [2] + [0] * 19cnt = 1x = (m - 1) // 2while x % 2 == 0:x //= 2i = 3while i**2 <= x:if x % i == 0:divs[cnt] = icnt += 1while x % i == 0:x //= ii += 2if x > 1:divs[cnt] = xcnt += 1g = 2while True:for i in range(cnt):if pow(g, (m-1)//divs[i], m) == 1:breakelse:return gg += 1def ceil_pow2(n):"""n <= 2**x を満たす最小のxを返却する。Parameters----------n : int0以上の整数Returns-------intn <= 2**x を満たす最小のx"""if n < 1:return 0return (n-1).bit_length()def bsf(n):"""自然数を2bitで表現したときに、右から見て最初に1が立つ桁が何桁目かを返却する。(0-indexed)Parameters----------n : int1以上の整数Returns-------int2bitで表現したときに、右から見て最初に1が立つ桁(0-indexed)"""return (n & -n).bit_length()-1MOD = 10**9 + 7class Convolution:"""畳み込みを行う。長さNの数列Aと長さMの数列Bから、長さ(N+M-1)の数列Cを計算する。c_i = sum_{j=0}^{i} a_j * b_{i-j}"""def __init__(self):self._first1 = Trueself._first2 = Trueself._sum_e = [0] * 30self._sum_ie = [0] * 30self._root = primitive_root(MOD)def _butterfly(self, a):n = len(a)h = ceil_pow2(n)if self._first1:self._first1 = Falsees = [0] * 30ies = [0] * 30m = MOD - 1cnt2 = bsf(m)e = pow(self._root, m >> cnt2, MOD)ie = pow(e, MOD - 2, MOD)for i in range(cnt2 - 1)[::-1]:es[i] = eies[i] = iee *= ee %= MODie *= ieie %= MODnow = 1for i in range(cnt2 - 1):self._sum_e[i] = es[i] * now % MODnow *= ies[i]now %= MODfor ph in range(1, h + 1):w = 1 << (ph - 1)p = 1 << (h - ph)now = 1for s in range(w):offset = s << (h - ph + 1)for i in range(p):left = a[i + offset]right = a[i + offset + p] * nowa[i + offset] = (left + right) % MODa[i + offset + p] = (left - right) % MODnow *= self._sum_e[bsf(~s)]now %= MODdef _butterfly_inv(self, a):n = len(a)h = ceil_pow2(n)if self._first2:self._first2 = Falsees = [0] * 30ies = [0] * 30m = MOD - 1cnt2 = bsf(m)e = pow(self._root, m >> cnt2, MOD)ie = pow(e, MOD - 2, MOD)for i in range(cnt2 - 1)[::-1]:es[i] = eies[i] = iee *= ee %= MODie *= ieie %= MODnow = 1for i in range(cnt2 - 1):self._sum_ie[i] = ies[i] * now % MODnow *= es[i]now %= MODfor ph in range(1, h + 1)[::-1]:w = 1 << (ph - 1)p = 1 << (h - ph)inow = 1for s in range(w):offset = s << (h - ph + 1)for i in range(p):left = a[i + offset]right = a[i + offset + p]a[i + offset] = (left + right) % MODa[i + offset + p] = ((MOD + left - right) * inow % MOD)inow *= self._sum_ie[bsf(~s)]inow %= MODdef convolution(self, a, b):n = len(a)m = len(b)if n*m == 0:return []if min(n, m) <= 60:if n < m:n, m = m, na, b = b, ares = [0] * (n + m - 1)for i in range(n):for j in range(m):res[i + j] += a[i] * b[j]res[i + j] %= MODreturn resz = 1 << ceil_pow2(n + m - 1)a += [0] * (z - n)b += [0] * (z - m)self._butterfly(a)self._butterfly(b)for i in range(z):a[i] *= b[i]a[i] %= MODself._butterfly_inv(a)a = a[:n + m - 1]iz = pow(z, MOD - 2, MOD)for i in range(n + m - 1):a[i] *= iza[i] %= MODreturn aA = A + AC = [0] * (N+1)for r in R:C[N-r] += 1conv = Convolution()res = conv.convolution(A, C)print(*res[N:2*N])