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\) 的树，所有方案的权值和。这个状态是好转移的，因为转移只需要知道左儿子和右儿子的子树大小。
森林怎么办。
有个限制，整个森林节点数为 \(m\)。（\(inf\) 不算）
考虑生成函数。
不会。
算 \(f\) 是 \(O(n^2)\) 的。
然后要优化这一坨。
妈呀，好好看的式子。
不是很会卷积，这个应该可以卷吧。那么一个 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();
}