Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
For a fixed permutation, ask: for which subarrays is position the minimum? The answer only depends on the closest smaller element on the left and on the right.
Build the min Cartesian tree of the permutation. If node has left subtree size and right subtree size , then
So the array describes allowed subtree sizes, not the actual values directly.
For a fixed Cartesian tree shape, the permutation values are not always unique. If the root has subtree sizes and , after putting the smallest value at the root, you choose which of the remaining values go left:
A direct interval DP would be
where must satisfy . But enumerating all roots is the trap. Reverse the transition.
If you already know a valid interval of length and want it to be a child of an adjacent root , then the sibling length is forced:
Process valid intervals by increasing length, start with leaves , hash intervals, and generate parents only from the larger child; if both children have equal length, generate only from the right child. Boom, no divisor circus.
For position , let
Then is the minimum of exactly those subarrays whose left end is in and right end is in , hence
In the min Cartesian tree of , the subtree of node is exactly the interval
So if node has left subtree size and right subtree size , then
This is the main translation. We are counting Cartesian tree shapes over fixed inorder positions, plus valid heap-labelings.
Let be the number of valid Cartesian subtrees on interval , using the given values. Empty intervals have value .
If is the root of , define
The root is allowed iff
For a fixed shape, after assigning the smallest value to the root, we choose which of the remaining values go into the left subtree. Therefore the transition is
Naively this is awful. We need to avoid scanning roots for every interval.
Suppose we already know that interval is valid, and its length is .
Then its parent root must be . If the right sibling has length , then
So is forced:
If this is an integer and the right sibling interval is already known, we can create the parent interval.
Symmetrically, the parent root must be , and the left sibling length is forced by the same formula.
This is the whole trick: do not enumerate divisors or roots. Every known interval tries only two possible parents.
A parent length is always
which is strictly larger than both child lengths. So we process intervals by increasing length.
There is one duplicate danger: a parent can be discovered from its left child and also from its right child. We use this clean rule:
Thus every transition is applied exactly once. No double-counting, no funny business.
Leaves are exactly intervals of length , and they are valid iff
Every subarray has exactly one minimum, so for any valid permutation
Also, since with , we must have
If either check fails, the answer is immediately .
Let be the number of generated non-empty valid intervals. Each interval is inserted once and tries at most two reverse transitions. Hash table lookups are expected .
So the running time is
and memory is
In practice is small because we only generate genuinely reachable subtree intervals; the fake divisor-pair ocean is never touched. This is exactly why the reverse transition matters.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1'000'000'007;
const int MAXN = 500000;
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
vector<int> fact, ifact;
int C(int n, int k) {
if (k < 0 || k > n) return 0;
return (ll)fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}
struct CustomHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int main() {
setIO();
fact.assign(MAXN + 1, 1);
ifact.assign(MAXN + 1, 1);
for (int i = 1; i <= MAXN; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
ifact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) ifact[i - 1] = (ll)ifact[i] * i % MOD;
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<ll> a(n + 2, 0);
ll sum = 0;
bool bad = false;
ll s = n + 1LL;
ll maxProd = (s / 2) * ((s + 1) / 2); // floor((n+1)^2 / 4)
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
if (a[i] > maxProd) bad = true;
}
ll need = 1LL * n * (n + 1) / 2;
if (bad || sum != need) {
cout << 0 << '\n';
continue;
}
vector<vector<int>> bucket(n + 1);
unordered_map<ll, int, CustomHash> dp;
dp.reserve(4 * n + 10);
dp.max_load_factor(0.7);
auto keyOf = [&](int l, int len) -> ll {
return 1LL * len * (n + 2) + l;
};
auto getVal = [&](int l, int len) -> int {
if (len == 0) return 1;
auto it = dp.find(keyOf(l, len));
if (it == dp.end()) return 0;
return it->second;
};
auto addInterval = [&](int l, int len, int val) {
if (val == 0) return;
ll key = keyOf(l, len);
auto it = dp.find(key);
if (it == dp.end()) {
dp.emplace(key, val);
bucket[len].push_back(l);
} else {
int nv = it->second + val;
if (nv >= MOD) nv -= MOD;
it->second = nv;
}
};
// Leaves.
for (int i = 1; i <= n; i++) {
if (a[i] == 1) addInterval(i, 1, 1);
}
for (int len = 1; len <= n; len++) {
for (int l : bucket[len]) {
auto itCur = dp.find(keyOf(l, len));
if (itCur == dp.end()) continue;
int cur = itCur->second;
if (cur == 0) continue;
int r = l + len - 1;
ll denom = len + 1LL;
// Current interval is the left child of root x = r + 1.
int x = r + 1;
if (x <= n && a[x] % denom == 0) {
ll q = a[x] / denom; // rightLen + 1
if (1 <= q && q <= n - x + 1LL) {
int rightLen = (int)q - 1;
// Generate only from the larger child. Equal case belongs to right child.
if (rightLen < len) {
int other = getVal(x + 1, rightLen);
if (other) {
int ways = C(len + rightLen, len);
int add = (ll)cur * other % MOD * ways % MOD;
addInterval(l, len + rightLen + 1, add);
}
}
}
}
// Current interval is the right child of root x = l - 1.
x = l - 1;
if (x >= 1 && a[x] % denom == 0) {
ll q = a[x] / denom; // leftLen + 1
if (1 <= q && q <= x) {
int leftLen = (int)q - 1;
// Larger child generates; if equal, the right child generates.
if (leftLen <= len) {
int start = x - leftLen;
int other = getVal(start, leftLen);
if (other) {
int ways = C(leftLen + len, leftLen);
int add = (ll)other * cur % MOD * ways % MOD;
addInterval(start, leftLen + len + 1, add);
}
}
}
}
}
}
cout << getVal(1, n) << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1'000'000'007;
const int MAXN = 500000;
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
vector<int> fact, ifact;
int C(int n, int k) {
if (k < 0 || k > n) return 0;
return (ll)fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}
struct CustomHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int main() {
setIO();
fact.assign(MAXN + 1, 1);
ifact.assign(MAXN + 1, 1);
for (int i = 1; i <= MAXN; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
ifact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) ifact[i - 1] = (ll)ifact[i] * i % MOD;
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<ll> a(n + 2, 0);
ll sum = 0;
bool bad = false;
ll s = n + 1LL;
ll maxProd = (s / 2) * ((s + 1) / 2); // floor((n+1)^2 / 4)
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
if (a[i] > maxProd) bad = true;
}
ll need = 1LL * n * (n + 1) / 2;
if (bad || sum != need) {
cout << 0 << '\n';
continue;
}
vector<vector<int>> bucket(n + 1);
unordered_map<ll, int, CustomHash> dp;
dp.reserve(4 * n + 10);
dp.max_load_factor(0.7);
auto keyOf = [&](int l, int len) -> ll {
return 1LL * len * (n + 2) + l;
};
auto getVal = [&](int l, int len) -> int {
if (len == 0) return 1;
auto it = dp.find(keyOf(l, len));
if (it == dp.end()) return 0;
return it->second;
};
auto addInterval = [&](int l, int len, int val) {
if (val == 0) return;
ll key = keyOf(l, len);
auto it = dp.find(key);
if (it == dp.end()) {
dp.emplace(key, val);
bucket[len].push_back(l);
} else {
int nv = it->second + val;
if (nv >= MOD) nv -= MOD;
it->second = nv;
}
};
// Leaves.
for (int i = 1; i <= n; i++) {
if (a[i] == 1) addInterval(i, 1, 1);
}
for (int len = 1; len <= n; len++) {
for (int l : bucket[len]) {
auto itCur = dp.find(keyOf(l, len));
if (itCur == dp.end()) continue;
int cur = itCur->second;
if (cur == 0) continue;
int r = l + len - 1;
ll denom = len + 1LL;
// Current interval is the left child of root x = r + 1.
int x = r + 1;
if (x <= n && a[x] % denom == 0) {
ll q = a[x] / denom; // rightLen + 1
if (1 <= q && q <= n - x + 1LL) {
int rightLen = (int)q - 1;
// Generate only from the larger child. Equal case belongs to right child.
if (rightLen < len) {
int other = getVal(x + 1, rightLen);
if (other) {
int ways = C(len + rightLen, len);
int add = (ll)cur * other % MOD * ways % MOD;
addInterval(l, len + rightLen + 1, add);
}
}
}
}
// Current interval is the right child of root x = l - 1.
x = l - 1;
if (x >= 1 && a[x] % denom == 0) {
ll q = a[x] / denom; // leftLen + 1
if (1 <= q && q <= x) {
int leftLen = (int)q - 1;
// Larger child generates; if equal, the right child generates.
if (leftLen <= len) {
int start = x - leftLen;
int other = getVal(start, leftLen);
if (other) {
int ways = C(leftLen + len, leftLen);
int add = (ll)other * cur % MOD * ways % MOD;
addInterval(start, leftLen + len + 1, add);
}
}
}
}
}
}
cout << getVal(1, n) << '\n';
}
return 0;
}