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

CF838D Airplane Arrangements

CF838D Airplane Arrangements

题意

有一架飞机,从前到后有 \(n\) 排座位。将会有 \(m\) 人登上这架飞机。

这架飞机的前面和后面都有一个入口。

每个人都有一个分配的座位。可能会有多个人被分配到同一个座位。人们将一个接一个地登机,从第 \(1\) 个人开始。每个人可以独立选择从前面入口或后面入口进入飞机。

当一个人走进飞机时,他们会直接走到他们分配的座位并尝试坐下。如果座位被占用,他们会继续朝着他们走进来的方向走,直到找到一个空座位——他们会选择第一个找到的空座位。如果他们到达排的尽头仍然没有找到座位,他们会感到愤怒。

找出为乘客分配座位并登机,且没有任何人生气的方案数量。如果存在一个乘客在两种方案中选择了不同的入口,或者分配的座位不同,则这两种方案是不同的。输出这个方案数对 \(10^9 + 7\) 取模的结果。

\(1 \le m \le n \le 1000000\),分别表示座位的数量和乘客的数量。

思路

做不出来的做法

我们认为座位是从左到右的。

如果直接以每个人分配的座位和选择的方向为状态,感觉非常难算和诡异。

不妨以每个人最终的座位为状态,计算每种状态有多少个方案。

\(i\) 个人的最终座位为 \(p_i\) 时,我们依次假如每个人,计算每个人有多少种方案,乘起来。第 \(i\) 个人的方案数只和前 \(i\) 个人的 \(p_i\) 有关,这个性质很优美。

第一个人可以从左/右进入,他分配的座位一定是 \(p_1\)。方案数为 \(2\)

如果 \(p_2\) 不挨着 \(p_1\),那么第二个人也可以从左/右进入,他分配的座位一定是 \(p_2\)。方案数为 \(2\)

\(i\) 个人,如果 \(p_i\) 左边连着 \(k\) 个位置已经被占用了,那么他可以从左边进入,分配到 \([p_i-k,p_i]\)。右边同理。

因此得出结论,第 \(i\) 个人的方案数是:设已经被占用的座位里,包含 \(p_i\) 的连续段长度为 \(len\),方案数为 \(len+1\)


我们自然地想要在位置上做。即设 \(q_i\) 表示位置 \(i\) 最后被谁坐了。

要是没人坐,就是被 \(inf\) 坐了。

对排列 \(q\) 建大根的笛卡尔树。

那么位置 \(i\) 的贡献就是 \(siz_i+1\)\(inf\) 坐的座位不用算贡献。

所以问题转化成数笛卡尔森林的个数,一棵笛卡尔树的权值是 \(\prod siz_u+1\)


我们先求一棵笛卡尔树的权值。再拓展到森林。

\(f_i\) 表示大小为 \(i\) 的树,所有方案的权值和。这个状态是好转移的,因为转移只需要知道左儿子和右儿子的子树大小。

\[f_0=1\\ f_i = (i+1) \sum_{j=0}^{i-1} f_j f_{i-j-1} \binom{i-1}{j} \]

森林怎么办。

有个限制,整个森林节点数为 \(m\)。(\(inf\) 不算)

考虑生成函数。

不会。


\(f\)\(O(n^2)\) 的。

然后要优化这一坨。

\[f_i = (i+1) (i-1)! \sum_{j=0}^{i-1} \frac{1}{j!} f_j \frac{1}{(i-j-1)!} f_{i-j-1} \]

妈呀,好好看的式子。

不是很会卷积,这个应该可以卷吧。那么一个 NTT 卷完就做完了。

这是一个自己卷自己的类型,参见 FFT 相关。

那么总时间复杂度 \(O(n \log^2 n)\)

可是 \(10^6\)\(2s\),不太能过的样子。

看看题解,有没有不用多项式的做法呢?

怎么全是简洁优美的组合数。还是要学好组合。

这篇题解写得很清楚。

妈呀,怎么这么牛!

转化成每个人随机方向和机票,求方案合法的概率。

发现无从下手。

看成一个环形的座位,从 \(1\)\(n\) 进入,方向是顺时针或者逆时针。在 \(1,n\) 衔接的地方放一个座位 \(0\)。如果有人最终坐到了 \(0\),方案不合法。

环长为 \(n+1\),每个人随机分配座位和方向,求最后 \(0\) 没有被占用的概率。

因为每个座位显然是等价的。一个座位被占据的概率是 \(\frac{m}{n+1}\)。所以概率为 \(\text{方案总数} \times \frac{n+1-m}{n+1} = (2(n+1))^m \times \frac{n+1-m}{n+1}\)

code

CF 题真是思维题。怎么能想到的啊。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {constexpr int N=1e6+7,mod=1e9+7;struct modint {int x;modint (int y=0) : x(y) {}modint operator + (modint b) const { return x+b.x<mod ? x+b.x : x+b.x-mod; }modint operator * (modint b) const { return 1ll*x*b.x%mod; }modint &operator += (modint b) { return *this = *this + b; }modint &operator *= (modint b) { return *this = *this * b; }modint inv() {modint s=1, a=*this;int b=mod-2;while(b) {if(b&1) s*=a;a*=a;b>>=1;}return s;}void write() { pf("%d\n",x); }} ans;int n,m;void main() {sf("%d%d",&n,&m);ans=n+1-m;ans*=(modint){n+1}.inv();rep(i,1,m) ans*=n+1, ans+=ans;ans.write();}
}
int main() {#ifdef LOCALfreopen("in.txt","r",stdin);freopen("my.out","w",stdout);#endifwing_heart :: main();
}
http://www.hskmm.com/?act=detail&tid=19995

相关文章:

  • java操作数据库中的bug
  • 事务和Spring常用注解的总结
  • 浅谈SQL应用考试,临时抱佛脚篇
  • 网络安全风险评估指南:CISO如何通过风险评估提升安全防护
  • 藏好自己,做好清理——悼念沈劫匪先生有感
  • macbook m1 安装telnet
  • 低空经济:从政策热词到生活日常——中国低空经济全景解析与杭深模式对比 - 教程
  • 指数函数的特征
  • 生猪
  • git merge driver简介
  • 在 Linux 中安装和配置 NTP 服务器和 NTP 客户端
  • Android15音频进阶之车载多音区调整解析(一百三十七)
  • 微信二次开发社群机器人接口
  • FireDAC(Master-Detail 功能)主从表查询
  • 极氪汽车火山引擎:AI数据专家“上岗”,注入“分钟级”数据洞察力
  • C++面试宝典 01 new/delete/malloc/free关系
  • Ansible + Docker 部署 MinIO 集群
  • ​​万用表与电流探头测量电流信号的技术对比分析​​
  • flink运行时架构 - --
  • k8s命令
  • wifi亮灭屏机制--系统修改
  • 自动遍历测试利器:开源工具AppCrawler 配置全解析
  • 得帆云ETL全新版本升级驱动数据高效流转
  • Windows 的图标没有及时更新
  • 拒绝 “能源糊涂账”!MyEMS 如何让中小企业能耗管理 “秒上手”?
  • 【海内外多个支持单位|学生优惠|高录用快见刊】第五届管理科学和软件工程国际学术会议(ICMSSE 2025)
  • 电天下dq123.com搜索功能全新升级,AI加持,焕新垂直行业搜索体验!
  • 中小微企业能源管理 “入门神器”:MyEMS 开源系统如何低成本实现专业级管控?
  • jinja2和角色管理和集合
  • 挖同行墙脚!有稳定供应商的客户怎么下手构建?