Submission #896446

#TimeUsernameProblemLanguageResultExecution timeMemory
896446AlcabelŽarulje (COI15_zarulje)C++17
0 / 100
75 ms10936 KiB
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; struct Modint { int x; Modint() { x = 0; } Modint(int _x) { while (_x >= mod) { _x -= mod; } while (_x < 0) { _x += mod; } x = _x; } Modint(long long _x) { if (_x >= mod || _x <= -mod) { _x %= mod; } if (_x < 0) { _x += mod; } x = _x; } Modint operator+(const Modint& other) const { return Modint(x + other.x); } Modint operator*(const Modint& other) const { return Modint(x * 1ll * other.x); } void operator+=(const Modint& other) { *this = *this + other; } void operator*=(const Modint& other) { *this = *this * other; } Modint operator^(long long p) const { Modint res = 1, tmp = x; while (p > 0) { if (p & 1) { res *= tmp; } tmp *= tmp; p >>= 1; } return res; } Modint operator/(const Modint& other) const { return *this * (other ^ (mod - 2)); } void operator/=(const Modint& other) { *this = *this / other; } ~Modint() {} }; vector<Modint> fact, invFact; void buildFact(int n) { fact.resize(n + 1); invFact.resize(n + 1); fact[0] = 1; for (int i = 1; i <= n; ++i) { fact[i] = fact[i - 1] * i; } invFact[n] = fact[n] ^ (mod - 2); for (int i = n; i > 0; --i) { invFact[i - 1] = invFact[i] * i; } } Modint C(int n, int k) { if (n < 0 || k < 0 || n < k) { return 0; } return fact[n] * invFact[k] * invFact[n - k]; } void solve() { int n, k; cin >> n >> k; buildFact(n); vector<int> a(n), order(n); for (int i = 0; i < n; ++i) { cin >> a[i]; order[i] = i; } sort(order.begin(), order.end(), [&](const int& A, const int& B) { return a[A] < a[B]; }); vector<vector<int>> byVal(n); int difs = 0; for (int l = 0, r; l < n; ++l, ++difs) { r = l - 1; while (r + 1 < n && a[order[r + 1]] == a[order[l]]) { ++r; byVal[difs].emplace_back(order[r]); } l = r; } vector<Modint> ans(n, Modint(1)); set<int> borders = {-1, n}; vector<Modint> modif(n, 1); for (int val = 0; val < difs; ++val) { int sz = byVal[val].size(); // cerr << "val: " << a[byVal[val][0]] << '\n'; for (int pos = 0, posL = 0, posR = 0; pos < sz; ++pos) { // cerr << "idx: " << byVal[val][pos] << '\n'; auto it = borders.upper_bound(byVal[val][pos]); int bR = *it, bL = *(--it); while (byVal[val][posL] <= bL) { ++posL; } while (posR < sz && byVal[val][posR] < bR) { ++posR; } // cerr << "posL: " << posL << ", posR: " << posR << '\n'; assert(posL <= pos && pos < posR); ans[byVal[val][pos]] *= C(posR - posL - 1, pos - posL); if (pos != 0) { if (byVal[val][pos - 1] > bL) { // [byVal[val][pos - 1] + 1, byVal[val][pos] - 1] modif[byVal[val][pos - 1] + 1] *= C(posR - posL, posR - pos); modif[byVal[val][pos]] /= C(posR - posL, posR - pos); } if (it != borders.begin() && *prev(it) < byVal[val][pos - 1]) { int prevPosL = upper_bound(byVal[val].begin(), byVal[val].end(), *prev(it)) - byVal[val].begin(); // cerr << "!\n"; ans[bL] *= C(posR - prevPosL, posR - pos); } } } for (const int& i : byVal[val]) { borders.insert(i); } } for (int i = 0; i < n; ++i) { ans[i] *= modif[i]; } while (k--) { int pos; cin >> pos; --pos; cout << ans[pos].x << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...