当前位置: 首页 > news >正文

题解:AT_arc138_f [ARC138F] KD Tree

题意:平面上有 \(n\) 个点 \((i,p_i)\)\(p\) 是一个排列。每次操作可以选择 \(x/y\) 和一个坐标,将点列分成左右/上下两边(保持两边的相对顺序不变),分别递归下去,直到只剩下一个点,把它加入答案序列末尾。求最终能生成多少种不同的答案序列。

做法:

首先很自然地考虑目前剩下的矩形为 \(x\in[l,r],y\in[u,d]\),记此时的答案为 \(f_{l,r,u, d}\)。考虑一刀劈成两半继续递归,但是显然这样直接算是错的,考虑如下情况:

  • 只有 \((1,1),(2,2)\) 两个点。

此时你做对 \(x\) 轴和 \(y\) 轴的操作是没有区别的。

那么对于这种会重复的我们一般考虑加一些限制使他不会重复。这里我们先定义一些东西,考虑现在这个区域中剩下了 \(k+1\) 个点,离散后应该会剩下 \(x_1<x_2<\cdots <x_k\)\(y_1<y2<\cdots <y_k\) 这些 切割线是有用的。我们考虑这么定义一个操作的字典序,按字典序从小到大排是 \(x_1,y_1,x_2,y_2,\cdots,x_k,y_k\)。这样排有什么好处呢?按字典序我们就可以让一种答案序列对应唯一一种操作序列,同时交错排布会有利于我们之后的分讨。

考虑如果一个操作序列第一刀切在的 \(x_i\) 这个位置,我们先算出来切在这里的总方案数,为 \(f_{l,x_i,u,d}\times f_{x_i+1, r,u,d}\)。但是有可能有操作序列字典序更小的得到了这个答案序列,考虑是 \(x_j\) 还是 \(y_j\)

  • \(x_j(j<i)\) 得到。

画图,那么应该分为这么几块:

那么形如 ABC 这样的操作序列就会被 \(x_j\) 解决而不是 \(x_i\),三部分方案乘起来即可。

  • \(y_j (j<i)\) 得到。

这样会分成四块:

考虑 \(x_i,y_j\) 分别切出来的顺序会是怎样,\(x_i\) 会是 (AB)(DC),\(y_j\) 会是 (AD)(BC)。考虑什么时候会重复计算,发现只能是 \(D\) 为空的时候我们才会记重,所以就必须得满足 \(D\) 为空才会减去。

\(y\) 的同样讨论,读者可以自己推一下。

到这里已经可以写了,只不过写起来需要分讨很多。我们这里其实会发现一个事情,就是假设我们 \(x\in[l,r],y\in[u,d]\) 的矩形包含了集合为 \(S\) 的点,那么令 \(Tx_i\) 代表 \(x_i\) 下方切出来的部分,\(Ty\) 类似定义,那么我们考虑按照字典序扫描,那么只有前面的是后面的子集的时候才会被重复统计,其实感觉也是比较显然的。那么这样就可以比较方便地实现了。因为这些集合都是矩形交出来的,所以其实只有 \(O(n^4)\) 个,不用担心状态过多。

总复杂度 \(O(n^6)\)

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 35, mod = 1e9 + 7;
int n, p[maxn], q[maxn];
map<int, int> mp;
int popcnt(int x) {int cnt = 0;while(x)cnt += x % 2, x >>= 1;return cnt;
}
int cnt = 0;
int cal(int s) {if(popcnt(s) <= 1)return mp[s] = 1;if(mp.count(s))return mp[s];
//	cnt++;
//	if(cnt <= 10)
//		cout << s << endl;vector<int> x, y;for (int i = 1; i <= n; i++) {if((s >> i - 1) & 1)x.push_back(i), y.push_back(p[i]);} sort(y.begin(), y.end());vector<int> t;int nw1 = 0, nw2 = 0;for (int i = 0; i < x.size() - 1; i++) {nw1 |= (1 << x[i] - 1);t.push_back(nw1);nw2 |= (1 << q[y[i]] - 1);t.push_back(nw2);//	if(cnt <= 5);//		cout << s << " " << nw1 << " " << nw2 << endl;}vector<int> dp; dp.resize(t.size());int ans = 0;for (int i = 0; i < t.size(); i++) {dp[i] = cal(t[i]);for (int j = 0; j < i; j++)if((t[i] & t[j]) == t[j])dp[i] = (dp[i] - dp[j] * cal(t[i] ^ t[j]) % mod + mod) % mod;ans += dp[i] * cal(s ^ t[i]) % mod; ans %= mod;}
//	cout << s << " " << ans << endl;return mp[s] = ans;
}
signed main() {cin >> n;for (int i = 1; i <= n; i++)cin >> p[i], q[p[i]] = i;cout << cal((1 << n) - 1) << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=28241

相关文章:

  • SP33 TRIP - Trip 个人题解
  • 经营不是老板一个人的事 - 智慧园区
  • Codeforces Round 1051 (Div. 2)[A ~E]
  • 如何在 Spring Boot 应用中配置多个 Spring AI 的 LLM 客户端
  • 使用eBPF技术保护FastAPI安全
  • 项目案例作业2:对案例进行面向对象分析
  • JavaSE
  • CF2064E Mycraft Sand Sort
  • Servlet笔记
  • 第一个博客
  • k8s 主节点重启后 从节点 get 异常 - 教程
  • 多维索引技术优化数据湖查询性能
  • Umi-OCR_文字识别工具 免安装使用教程(附下载安装包)!永久免费,开源离线OCR识别软件下载
  • 【汇总】OPPO r9m 分区名、分区功能
  • 04_线程池实现
  • #D251010D. 未命名 10 (unnamed)
  • 【JAVA】从入门到放弃-01-HelloWorld - 指南
  • 离线应用程序
  • 2025表面瑕疵检测厂家TOP5推荐:表面瑕疵检测,薄膜瑕疵检测,瑕疵检测设备,瑕疵在线检测,铝箔瑕疵在线检测,外观瑕疵检测机,薄膜瑕疵检测仪,陶瓷膜瑕疵检测各种类型检测,精准高效的质量守护
  • 表格识别:不仅能识别文字,更能理解表格的结构和逻辑关系,实现输出可编辑、可分析的结构化数据
  • 同步FIFO
  • P13274 [NOI2025] 三目运算符
  • Microsoft Office不小心卸载或重装系统后,如何重新安装 ... - sherlock
  • HTTPS 抓包乱码怎么办?原因剖析、排查步骤与实战工具对策(HTTPS 抓包乱码、gzipbrotli、TLS 解密、iOS 抓包) - 实践
  • 使用JaCoCo进行代码覆盖率分析
  • 计算机视觉专家入选德国国家科学院
  • 2025 年工程管理软件/软件系统/软件App/软件平台/工程管理软件和验房系统公司/企业推荐榜:数字化转型下的实用选型指南
  • 【Java学习】【Java基础】--第1篇:入门Java和对面向对象的理解
  • solutions
  • 技术面:Spring (事务传播机制、事务失效的原因、BeanFactory和FactoryBean的关系)