ARC138F 题解

· · 题解

Problem Link

题目大意

给定 n 个点 (1,a_1)\sim (n,a_n)，a 是 1\sim n 排列，你要对这个点集进行若干次操作，得到一个序列。

如果 n=1，序列中只含有这个点，否则选择如下两种操作之一：

  • 选择一个 x，把 i<x 的点操作得到的序列和 x\le i 的点操作得到的序列拼起来。
  • 选择一个 y，把 a_i<y 的点操作得到的序列和 y\le a_i 的点操作得到的序列拼起来。

求有能得到多少种不同的序列。

数据范围：n\le 30。

思路分析

计数操作序列是容易的，直接 f_{l,r,u,d} 表示 x,y 两维的范围，求出这个范围内的点列有多少种划分方式。

但我们无法把操作序列和结果序列建立对应，考虑对一个若干等价的操作序列定义代表元。

对于一组结果序列，我们定义其代表元为每次操作贪心地取字典序最小的一个时的操作序列，其中所有操作的字典序按如下顺序排列：x=2,y=2,x=3,\dots,x=n,y=n。

考虑 f_{1,n,1,n} 如何计算。

那么我们 dp 时枚举最小操作 x=i，那么就会递归成 f_{1,i-1,1,n} 和 f_{i,n,1,n} 两部分，但我们要在 f_{1,i-1,1,n} 范围内钦定 x=i 是最小字典序操作，设方案数为 g_i。

不妨容斥，设 x=j 是实际最小字典序操作，那么最终的结果序列一定会被分成 x\in [1,j),x\in [j,i),x\in[i,n] 三部分，g_i 就要减去 f_{1,j-1,1,n}\times f_{j,n,1,n}。

同理如果 y=j 是最小字典序操作，此时一定有 j<i，那么 y=j 时划分出的左部点集大小小于 x=i 时的左部点集。

如果想让得到的结果序列相同，则 y=j 时划分出的左部点集必须是 x=i 时划分出的左部点集的子集，类似可以划分子问题计算。

注意我们枚举的操作一定是非平凡操作，即 x/y 恰好是某个点的横坐标或纵坐标。

不断递归子问题即可，可以用记忆化搜索实现，用状压记录状态比较好写。

时间复杂度 \mathcal O(n^6)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
int n,a[35];
unordered_map <int,ll> Q;
ll dp(int s) {
    if(Q.count(s)) return Q[s];
    if(__builtin_popcount(s)<=1) return 1;
    vector <int> xi,yi;
    for(int i=0;i<n;++i) if(s>>i&1) xi.push_back(i),yi.push_back(i);
    sort(yi.begin(),yi.end(),[&](int i,int j){ return a[i]<a[j]; });
    int k=xi.size();
    vector <int> st;
    for(int i=0,xt=0,yt=0;i<k-1;++i) {
        st.push_back(xt|=1<<xi[i]);
        st.push_back(yt|=1<<yi[i]);
    }
    vector <ll> f(2*k-2);
    ll ans=0;
    for(int i=0;i<2*k-2;++i) {
        f[i]=dp(st[i]);
        for(int j=0;j<i;++j) if((st[j]&st[i])==st[j]) f[i]=(f[i]-f[j]*dp(st[i]^st[j]))%MOD;
        if(f[i]<0) f[i]+=MOD;
        ans=(ans+f[i]*dp(s^st[i]))%MOD;
    }
    return Q[s]=ans;
}
signed main() {
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);
    printf("%lld\n",dp((1<<n)-1));
    return 0;
}