题解归档 - cf2234E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2234E
• 本地来源：problems/cf2234E/idea.md
• 题目链接：https://codeforces.com/contest/2234/problem/E
• 原始标题：cf2234E - Vlad, Misha and Two Arrays

思路

cf2234E - Vlad, Misha and Two Arrays

pattern:
Cartesian tree / divide and conquer counting

claim:
For a permutation p, the value written at position i is
(i - L) * (R - i), where L and R are the nearest positions on the left
and right with value smaller than p[i].

why:
Subarrays whose minimum is p[i] must contain i and cannot cross a smaller
value. Inside the open interval (L,R), every subarray containing i has
minimum at i exactly when p[i] is the smallest remaining value of the
current interval.

count:
Process an interval (L,R). Its minimum position must be some pos with
a[pos] == (pos-L)*(R-pos). If none exists, the array is impossible. The
relative order of values is equivalent to a Cartesian tree. For every interval
of length len, the set of values assigned to that interval can be split among
the chosen root and its children in len equivalent placements, so the final
count is:

n! / product(len over all recursive intervals).

implementation:
The current solver finds one valid root per interval by scanning from both ends,
multiplies the denominator by the interval length, and pushes the two
subintervals onto an explicit stack. The explicit stack avoids recursion depth
issues on monotone Cartesian trees.

check:
brute.cpp enumerates all permutations for small n, computes their arrays,
and counts matches. Random generator mixes valid arrays from random
permutations and arbitrary arrays.

代码

来源：problems/cf2234E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:30:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=500005;
const ll mod=1000000007;
ll a[maxn+5],t,n,i,cur,ans,pd,dq;
ll pw(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
void solveIntervals(){
    ll L,R,len,le,ri,need,pos;
    vector<pair<ll,ll>> st;
    st.push_back({0,n+1});
    while(!st.empty() and dq){
        L=st.back().first;
        R=st.back().second;
        st.pop_back();
        if(L+1>R-1) continue;
        len=R-L-1;
        pd=pd*len%mod;
        le=L+1;
        ri=R-1;
        pos=-1;
        while(le<=ri){
            need=(le-L)*(R-le);
            if(a[le]==need){
                pos=le;
                break;
            }
            need=(ri-L)*(R-ri);
            if(a[ri]==need){
                pos=ri;
                break;
            }
            le++;
            ri--;
        }
        if(pos==-1){
            dq=0;
            break;
        }
        st.push_back({L,pos});
        st.push_back({pos,R});
    }
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>a[i];
        dq=1;
        pd=1;
        solveIntervals();
        if(!dq){
            cout<<"0\n";
            continue;
        }
        ans=1;
        for(i=1;i<=n;i++) ans=ans*i%mod;
        ans=ans*pw(pd,mod-2)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}