题解：CF2234E Vlad, Misha and Two Arrays

xyy_xxyy · 2026-11-11 09:13:38 · 题解

联考 T1，没有写出来，急哭了。

首先通过手摸不难发现一个性质：当 a_i=i \times (n - i + 1) 时，a_i 就是区间 [1,n] 的最小值。这个推广到任何区间都是成立的，形如当 a_i=(i - l + 1) \times (r - i + 1) 时，a_i 为区间 [l,r] 的最小值。

发现了这个性质之后这道题就好做了，我们考虑分治，定义 f(l,r) 为区间 [l,r] 的答案，对于现在的区间 [l, r]，暴力扫最小值在哪里，假设我们找到的位置为 mid，那么答案怎么算呢？这个其实很简单，你找到了最小值后，这两个区间就是独立的了，所以我们可以往里面随便填数，所以答案就是 f(l,mid-1) \times f(mid + 1, r) \times C_{mid-l}^{r-l}。恭喜你学会了 O(n^2) 的做法。

考虑优化，这个就不太好想了。我们从两边用两个指针往中间扫去找最小值，感性理解一下，如果我找到最小值很快，那么我进入下一层的时间复杂度也不会太多。但如果找到最小值很慢，说明最小值大概在中间，把两边分开了，下一层的时间复杂度也不会很多。综合以下大致是 O(n \log _2 n) 的。

实现中会有一些判 0 的情况，可以参考以下代码。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5, mod = 1e9 + 7;
int a[N], jc[N], jcny[N], n;
int ksm(int x, int y) {
    int res = 1;
    while (y != 0) {
        if (y & 1) { 
            res = res * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return res;
} 
int C(int n, int m) {
    return jc[n] * jcny[m] % mod * jcny[n - m] % mod;
}
bool check(int l, int mid, int r) {
    if (a[mid] == (mid - l + 1) * (r - mid + 1)) {
        return 1;
    }
    return 0;
}
int f(int l, int r) {
    // cout << l << ' ' << r << '\n';
    if (l > r) {
        return 1;
    }
    if (l == r) {
        if (a[l] == 1) {
            return 1;
        }
        return 0;
    }
    int L = l, R = r;
    while (L <= R) {
        if (check(l, L, r)) {
            // cout << "QWQ1 " << L << '\n';
            return f(l, L - 1) * f(L + 1, r) % mod * C(r - l, L - l) % mod;
        }
        if (check(l, R, r)) {
            // cout << "QWQ2 " << R << '\n' << f(l, R - 1) << ' ' << f(R + 1, r) << ' ' << C(r - l, R - l) << '\n';
            return f(l, R - 1) * f(R + 1, r) % mod * C(r - l, R - l) % mod;
        }
        L++;
        R--;
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("cerydra.in", "r", stdin);
    // freopen("cerydra.out", "w", stdout);
    jc[0] = 1;
    jcny[0] = 1;
    for (int i = 1; i <= 5e5; i++) {
        jc[i] = jc[i - 1] * i % mod;
        jcny[i] = ksm(jc[i], mod - 2);
        // cout << jc[i] << ' ' << jcny[i] << '\n';
    }
    // cout << ksm(2, 4) << "???\n"; 
    // cout << C(3, 1) << "???\n"; 
    int T = 1;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }  
        cout << f(1, n) << '\n';
    }
    // cout << qwq << '\n';
    return 0;
}