結果
問題 | No.573 a^2[i] = a[i] |
ユーザー |
|
提出日時 | 2017-10-06 23:47:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 1,093 bytes |
コンパイル時間 | 102 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 26,496 KB |
最終ジャッジ日時 | 2024-11-17 02:16:15 |
合計ジャッジ時間 | 7,531 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
def init_factorials(N, mod): f = 1 fac = [1] * (N + 1) for i in range(1, N + 1): f *= i f %= mod fac[i] = f return fac def init_inv(N, mod, fac): b = bin(mod-2)[2:][-1::-1] ret = 1 tmp = fac[N] if b[0] == '1': ret = fac[N] for bi in b[1:]: tmp *= tmp tmp %= mod if bi == '1': ret *= tmp ret %= mod inv = [1] * (N + 1) inv[N] = ret for i in range(N-1, 0, -1): ret *= i + 1 ret %= mod inv[i] = ret return inv def nPb(n, b, mod, fac, inv): return (fac[n] * inv[n-b]) % mod def nCb(n, b, mod, fac, inv): return (fac[n] * inv[b] * inv[n-b]) % mod def f(r, c, mod, fac, inv): return (fac[r + c] * inv[r] * inv[c]) % mod def solve(n, mod, fac, inv): ans = 0 for i in range(1, n+1): ans += pow(i, n - i, mod) * nCb(n, i, mod, fac, inv) ans %= mod return ans N = 2 * 10**5 mod = 10**9 + 7 fac = init_factorials(N, mod) inv = init_inv(N, mod, fac) n = int(input()) print(solve(n, mod, fac, inv))