結果
問題 | No.797 Noelちゃんとピラミッド |
ユーザー |
|
提出日時 | 2019-03-15 23:03:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,479 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 73,472 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-07-01 21:28:45 |
合計ジャッジ時間 | 6,369 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
#include <algorithm> #include <iostream> #include <vector> #define MOD 1000000007 using namespace std; /* // vector template<typename T> struct combination { vector<T> fct, inv, finv; int mod; combination(int size, int newMod) { fct = vector<T>(size + 1, 1); inv = vector<T>(size + 1, 1); finv = vector<T>(size + 1, 1); mod = newMod; for (int i = 2; i <= size; ++i) { fct[i] = fct[i - 1] * i % mod; inv[i] = mod - mod / i * inv[mod % i] % mod; finv[i] = inv[i] * finv[i - 1] % mod; } } T combi(int n, int r) { return finv[n - r] * finv[r] % mod * fct[n] % mod; } }; */ struct combination { vector<long> fct, inv; long mod; long power(long m, long n, long mod) { if (n == 0) return 1; long res = power(m, n / 2, mod); if (n % 2) res = res * res % mod * m % mod; else res = res * res % mod; return res; } combination(int size, long newMod) { fct = vector<long>(size + 1, 1); inv = vector<long>(size + 1, 1); mod = newMod; for (int i = 1; i <= size; ++i) { fct[i] = fct[i - 1] * i % mod; inv[i] = power(fct[i], mod - 2, mod); } } long combi(long n, long r) { return fct[n] * inv[n - r] % mod * inv[r] % mod; } }; int main() { int N; cin >> N; vector<long> a(N); for (long& i : a) cin >> i; long sum = 0; combination cmb(N - 1, MOD); for (int i = 0; i < N; ++i) sum = a[i] * cmb.combi(N - 1, i) % MOD + sum % MOD; cout << sum % MOD; }