結果
問題 | No.856 増える演算 |
ユーザー |
![]() |
提出日時 | 2020-04-10 02:38:12 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,127 ms / 3,153 ms |
コード長 | 1,472 bytes |
コンパイル時間 | 517 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 60,004 KB |
最終ジャッジ日時 | 2024-09-14 05:57:07 |
合計ジャッジ時間 | 84,129 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 80 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 10 ** 9 + 7 def cumprod(A, MOD=MOD): L = len(A) Lsq = int(L**.5 + 1) A = np.resize(A, Lsq**2).reshape(Lsq, Lsq) for n in range(1, Lsq): A[:, n] *= A[:, n - 1] A[:, n] %= MOD for n in range(1, Lsq): A[n] *= A[n - 1, -1] A[n] %= MOD return A.ravel()[:L] def power(A, n): prod = np.ones_like(A, np.int64) powA = A.copy() for i in range(40): prod[n & 1 == 1] *= powA[n & 1 == 1] n >>= 1 powA **= 2 powA %= MOD prod %= MOD return prod def prod_1(A): fft = np.fft.rfft ifft = np.fft.irfft fft_len = 1 << 18 f = np.bincount(A) Ff = fft(f, fft_len) f = np.rint(ifft(Ff ** 2, fft_len)).astype(np.int64) np.add.at(f, A * 2, -1) f >>= 1 x = np.arange(len(f)) x = power(x, f) return cumprod(x)[-1] def prod_2(A): B = cumprod(A) x = power(B[:-1], A[1:].copy()) return cumprod(x)[-1] def find_min(A): B = np.minimum.accumulate(A)[:-1] C = A[1:] nums = np.log(B + C) + np.log(B) * C i = np.argmin(nums) b, c = int(B[i]), int(C[i]) return (b + c) * pow(b, c, MOD) % MOD N = int(readline()) A = np.array(read().split(), np.int64) a, b, c = map(int, (prod_1(A), prod_2(A), find_min(A))) answer = a * b * pow(c, MOD - 2, MOD) % MOD print(answer)