Submission #1841611
Source Code Expand
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <cmath> #include <queue> #include <map> #include <unordered_map> #include <set> #include <functional> using namespace std; typedef long long ll; vector<ll> fact(100005), fact_inv(100005); vector<int> appear(100005, 0); int l, r; ll mod = 1e9 + 7; ll func(ll n, ll p) { if (p == 1) return n; ll res = func(n, p / 2); res *= res; res %= mod; if (p % 2 == 1) return (res*n)%mod; return res; } int main() { int n; cin >> n; ll f = 1; fact[0] = fact_inv[0] = 1; for (int i = 1; i <= n + 1; ++i) { f *= i; f %= mod; fact.at(i) = f; fact_inv.at(i) = func(f, mod - 2); } for (int i = 1; i <= n; ++i) { int a; cin >> a; if (appear.at(a) != 0) { l = appear.at(a) - 1; r = n + 1 - i; } appear.at(a) = i; } cout << n << endl; for (int k = 2; k <= n; ++k) { ll ans = ((fact.at(n + 1) * fact_inv.at(k))%mod * fact_inv.at(n + 1 - k)) % mod; if (l + r >= k - 1) ans = (ans + mod - ((fact[l + r] * fact_inv[k - 1]) % mod * fact_inv[l + r - k + 1]) % mod) % mod; cout << ans << endl; } cout << 1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 11 |
User | yoshnary |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1196 Byte |
Status | AC |
Exec Time | 265 ms |
Memory | 3200 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | 1.txt, mx.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1.txt | AC | 265 ms | 3200 KB |
mx.txt | AC | 261 ms | 3200 KB |
rnd_0.txt | AC | 216 ms | 2944 KB |
rnd_1.txt | AC | 187 ms | 2944 KB |
rnd_2.txt | AC | 53 ms | 2432 KB |
rnd_3.txt | AC | 46 ms | 2304 KB |
rnd_4.txt | AC | 79 ms | 2432 KB |
sample1.txt | AC | 2 ms | 2176 KB |
sample2.txt | AC | 2 ms | 2176 KB |
sample3.txt | AC | 2 ms | 2176 KB |