結果
問題 |
No.573 a^2[i] = a[i]
|
ユーザー |
![]() |
提出日時 | 2020-01-01 18:41:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 850 ms / 2,000 ms |
コード長 | 908 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 48,124 KB |
最終ジャッジ日時 | 2024-11-22 14:28:06 |
合計ジャッジ時間 | 28,502 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np N = int(read()) 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 make_fact(U, MOD = MOD): x = np.arange(U, dtype = np.int64); x[0] = 1 fact = cumprod(x, MOD) x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD) fact_inv = cumprod(x, MOD)[::-1] return fact,fact_inv fact, fact_inv = make_fact(N+1) comb = fact[N] * fact_inv[:N+1] % MOD * fact_inv[:N+1][::-1] % MOD answer = 0 for i,c in enumerate(comb.tolist()): answer += c * pow(i,N-i,MOD) % MOD answer %= MOD print(answer)