题解：AT_arc138_f [ARC138F] KD Tree

kradcigam · 2024-11-27 16:18:04 · 题解

我们考虑记状态为 f_{l,r,u,d} 表示计算划分点集 S=\{i|l\le i\le r,u\le p_i\le d\} 的方案数。

注意到由于同一个点集排列可能有多种划分方式，则我们的思路是考虑计算字典序最小的划分方式。

此时，如何钦定操作的字典序就非常关键，这道题里的排列方式为：

• 我们将这个点集的横纵坐标离散化，假设有 k+1 个点，则有横纵坐标各有 k 个操作，为 x_1<x_2<\cdots<x_k 和 y_1<y_2<\cdots<y_k；
• 我们按照这样的顺序排列：x_1,y_1,x_2,y_2,\cdots,x_k,y_k。

我们记状态：

我们考虑转移：

• 首先假设当前计算字典序最小的操作是 x_i，那么我们考虑容斥，减去第一步字典序更小的方案：

  • 假设第一步字典序更小的操作为 x_j(j<i)，那么此时：

    方案数 ABC：fx_jf_{x_j+1,x_i,u,d}f_{x_i+1,r,u,d}；

  • 假设第一步字典序更小的操作为 y_j(j<i)，那么此时：

    • 先 x_i：（AC）（BD）；
    • 先 y_j：（CD）（AB）。

    注意到 j<i，C 部分不可能塞 i 个点，所以 A 部分必然不可能为空，于是如果存在方案，则必须要求 D 为空。

    方案为 CAB：fy_jf_{l,x_i,y_j+1,d}f_{x_i+1,r,yj+1,d}。

• 对于计算字典序最小的操作是 y_j，唯一的区别是：

  • 假设第一步字典序更小的操作为 x_i(i\le j)，那么此时：

    • 先 x_i：（AC）（BD）；

    • 先 y_j：（CD）（AB）。

    由于可能存在 i=j，所以 A 部分有可能为空，但注意到此时 \{t|p_t\le y_j\} 的点一定全放在了 C 部分，所以 D 部分为空。

    不难发现，此时令空点集方案数为 1，按照之前的计算方式要求 D 部分为空，仍然是正确的。

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

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x *= f;
}
const int N = 35, MOD = 1e9 + 7;
inline int& add(int &x, ll y) {return x = (x + y) % MOD;}
int n, p[N], q[N];
unordered_map <int, int> mp;
int dfs(int x) {
    if (__builtin_popcount(x) <= 1) return 1;
    if (mp.count(x)) return mp[x];
    vector <int> a, b;
    for (int i = 0; i < n; i++)
        if ((x >> i) & 1) a.push_back(i), b.push_back(p[i]);
    sort(all(b));
    vector <int> g;
    int s1 = 0, s2 = 0;
    F(i, 0, SZ(a) - 1) {
        g.push_back(s1 |= 1 << a[i]);
        g.push_back(s2 |= 1 << q[b[i]]);
    }
    vector <int> f(g.size());
    int ans = 0;
    F(i, 0, SZ(g)) {
        f[i] = dfs(g[i]);
        F(j, 0, i - 1)
            if ((g[i] & g[j]) == g[j]) add(f[i], MOD - (ll) f[j] * dfs(g[i] ^ g[j]) % MOD);
        add(ans, (ll) f[i] * dfs(x ^ g[i]));
    }
    return mp[x] = ans;
}
signed main() {
    read(n);
    for (int i = 0; i < n; i++) q[--read(p[i])] = i;
    cout << dfs((1 << n) - 1);
    return 0;
}