#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
75 ms |
10936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
