Submission #4024199
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = int64_t; using P = pair<ll, ll>; const ll INF = 5e15; const ll MOD = 1e9 + 7; class Combination { public: ll N; ll MOD; ll *fact; /* * MOD must be a prime number. */ Combination(ll N, ll MOD){ this->N = N; this->MOD = MOD; fact = new ll[N + 1]; fact[0] = 1; for(ll i = 1; i <= N; i++){ fact[i] = fact[i - 1] * i % MOD; } } ll pow(ll a, ll b){ return b ? (b & 1 ? a : 1) * pow(a * a % MOD, b / 2) % MOD : 1; } ll comb(ll n, ll k){ return fact[n] * pow(fact[n - k] * fact[k] % MOD, MOD - 2) % MOD; } }; int main(){ Combination C(1e5 + 10, MOD); ll N; cin >> N; vector<ll> W(N); for(ll &w : W) cin >> w; ll ans = 0; vector<ll> cnt(N + 1); for(ll i = 2; i <= N; i++) cnt[i] = C.fact[i - 1] * C.fact[N - i] % MOD * C.comb(N, i) % MOD; vector<ll> sum(N + 1); for(ll i = 2; i <= N; i++) (sum[i] += sum[i - 1] + cnt[i]) %= MOD; for(ll i = 0; i < N; i++){ (ans += W[i] * C.fact[N] % MOD) %= MOD; (ans += sum[i + 1] * W[i] % MOD) %= MOD; (ans += sum[N - i] * W[i] % MOD) %= MOD; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Removing Blocks |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1414 Byte |
Status | AC |
Exec Time | 137 ms |
Memory | 3328 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt |
All | sample-01.txt, sample-02.txt, sample-03.txt, sample-01.txt, sample-02.txt, sample-03.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 2 ms | 1024 KB |
sample-02.txt | AC | 2 ms | 1024 KB |
sample-03.txt | AC | 2 ms | 1024 KB |
subtask01-01.txt | AC | 2 ms | 1024 KB |
subtask01-02.txt | AC | 102 ms | 2816 KB |
subtask01-03.txt | AC | 80 ms | 2432 KB |
subtask01-04.txt | AC | 102 ms | 2816 KB |
subtask01-05.txt | AC | 36 ms | 1664 KB |
subtask01-06.txt | AC | 57 ms | 2048 KB |
subtask01-07.txt | AC | 35 ms | 1664 KB |
subtask01-08.txt | AC | 137 ms | 3328 KB |
subtask01-09.txt | AC | 137 ms | 3328 KB |
subtask01-10.txt | AC | 137 ms | 3328 KB |
subtask01-11.txt | AC | 137 ms | 3328 KB |
subtask01-12.txt | AC | 137 ms | 3328 KB |
subtask01-13.txt | AC | 137 ms | 3328 KB |