結果
問題 | No.797 Noelちゃんとピラミッド |
ユーザー |
![]() |
提出日時 | 2019-03-15 21:38:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 963 bytes |
コンパイル時間 | 1,676 ms |
コンパイル使用メモリ | 171,532 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 20:35:23 |
合計ジャッジ時間 | 6,288 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include "bits/stdc++.h" #define in std::cin #define out std::cout #define rep(i,N) for(LL i=0;i<N;++i) typedef long long int LL; const LL mod = 1000000007; // ユークリッドの互除法 LL extgcd(LL a, LL b, LL &x, LL &y) { LL g = a; x = 1; y = 0; if (b != 0) { g = extgcd(b, a%b, y, x); y -= (a / b)*x; } return g; } // 逆元 LL mod_inverse(LL a, LL m) { LL x, y; extgcd(a, m, x, y); return (m + x % m) % m; } // 階乗 std::vector<LL>fact; void mod_fact(LL n, LL m) { fact.resize(n + 1); fact[0] = 1; for (LL i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i%m; } // nCk mod p LL mod_comb(LL n, LL k, LL m) { if (n < k) return 0; return fact[n] * mod_inverse(fact[k] * fact[n - k] % m, m) % m; } int main() { LL N; in >> N; std::vector<LL>a(N); rep(i, N) in >> a[i]; LL ans = 0; mod_fact(N + 1, mod); rep(i, N) { LL temp = ((a[i] % mod)*mod_comb(N - 1, i, mod)) % mod; (ans += temp) %= mod; } out << ans << std::endl; }