#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int M = 1e6 + 25;
int add (int a, int b) {
a += b; if (a >= MOD) a -= MOD;
return a;
}
int sub (int a, int b) {
a -= b; if (a < 0) a += MOD;
return a;
}
int mul (int a, int b) {
return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
if (!b) return 1;
int u = power(a, b >> 1);
u = mul(u, u);
if (b & 1) u = mul(u, a);
return u;
}
int modinv (int x) {
return power(x, MOD - 2);
}
int fact[M], inv[M];
int nCr (int a, int b) {
if (a < b) return 0;
return mul(fact[a], mul(inv[b], inv[a - b]));
}
void pre () {
fact[0] = 1;
for (int i = 1; i < M; i++) {
fact[i] = mul(i, fact[i - 1]);
}
inv[M - 1] = power(fact[M - 1], MOD - 2);
for (int i = M - 2; i >= 0; i--) {
inv[i] = mul(i + 1, inv[i + 1]);
}
}
int n, k, a[M];
int qq[M];
int ans2[M];
map <int, int> changes[M];
void solve () {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= k; i++) {
cin >> qq[i];
}
stack <int> cur;
map <int, int> dd;
for (int i = 1; i <= n; i++) {
while (!cur.empty() && a[cur.top()] > a[i]) {
changes[i][a[cur.top()]]++;
dd[a[cur.top()]]--;
cur.pop();
}
changes[i][a[i]]--;
dd[a[i]]++;
cur.push(i);
}
while (!cur.empty()) {
cur.pop();
}
int L = 1;
map <int, int> ff;
for (auto j : changes[n]) {
dd[j.first] += j.second;
}
ans2[n] = 1;
for (int i = n - 1; i >= 1; i--) {
for (auto j : changes[i]) {
L = mul(L, modinv(nCr(ff[j.first] + dd[j.first], dd[j.first])));
dd[j.first] += j.second;
L = mul(L, nCr(ff[j.first] + dd[j.first], dd[j.first]));
}
while (!cur.empty() && a[cur.top()] > a[i + 1]) {
int x = a[cur.top()];
L = mul(L, modinv(nCr(ff[x] + dd[x], dd[x])));
ff[x]--;
L = mul(L, nCr(ff[x] + dd[x], dd[x]));
}
L = mul(L, modinv(nCr(ff[a[i + 1]] + dd[a[i + 1]], ff[a[i + 1]])));
ff[a[i + 1]]++;
L = mul(L, nCr(ff[a[i + 1]] + dd[a[i + 1]], ff[a[i + 1]]));
ans2[i] = L;
}
for (int i = 1; i <= k; i++) {
cout << ans2[qq[i]] << '\n';
}
}
signed main () {
pre();
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
55128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
65368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
55128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
