新年的军队题解人话重置版！
首先作一步相当重要的转化：
对所有满足恰有 m 个位置 i 满足 αi>αi+1 的实数序列 α1,α2,…,αn，计算 αk 的排名的分布。其中 αi 在 [0,1] 上均匀分布。
我们知道若干随机实数相等的概率是 0，所以这里其实区间的开闭也不影响结果。那么若干个实数就可以排出排名，并且显然每种排列出现的概率是相等的。
所以这个问题的结果和原问题是等价的。
然后稍微插入一下对概率密度函数的普及。
（我为啥要开个引用块？为了让会的神仙方便区分我的瞎扯和正经内容）
假装我们有一个在 [0,4] 上均匀分布的实数变量，考虑一个非常憨批的问题：其落在区间 [1,2] 内的概率。
我们发现这就是长度之比的事。
不过这个时候我们假装有一个在函数图像上的长方形，横坐标的范围是 [0,4]，纵坐标都是 14，然后我们在 [1,2] 上作定积分就得到了它的概率。
这个 14 其实就是个类似概率密度函数的东西。它用来描述连续型随机变量的输出值。我们想要知道它落在某个区间上的概率，只需要在这个区间上对概率密度函数作积分即可。
我们考虑用概率密度来考察特定 αk 的分布。若 αk 的排名为 j，则其贡献的概率密度即为 xj−1(1−x)n−j(j−1)!(n−j)!
这是因为当 αk=x 时，有 j−1 个数小于其的概率各是 x，然后它们有 (j−1)! 种排列方法，大于其的情况类似。
这个地方我们需要考虑除以 (j−1)! 的原因在于这些情况是本质相同的。
这样的话，刻画两个数之间的大小关系就变得容易了。因为我们可以直接在 [0,x] 或 [x,1] 上积分。
接下来我们建立所求的东西和概率密度函数的关系。
考虑令 ai 为 pi=i+1 的方案数，设 f(x) 为 αk 最终的概率密度函数，那么我们有 f(x)=n−1∑i=0aixi(1−x)n−1−ii!(n−1−i)!
容易反演 n−1∑i=0aixii!(n−1−i)!=n−1∑i=0fixi(1+x)n−1−i
具体地 n−1∑i=0fixi(1+x)n−1−i=n−1∑i=0(1+x)ifn−1−ixn−1−i=n−1∑i=0fn−1−ii∑j=0(ij)xn−1−(i−j)=n−1∑i=0fn−1−ii∑j=0(ij)xn−1−j=n−1∑j=0xn−1−jn−1∑i=j(ij)fn−1−i
接下来正式开始处理原问题。
考虑在概率密度函数中加入两个元区分大于号和小于号：设 F(u,v,t) 表示排列末尾的分布，其中 u 记录小于号，v 记录大于号。 F(t)=1+u∫t0F(τ)dτ+v∫1tF(τ)dτ
因此 F′=(u−v)F
显然可以待定系数得到其解 F=Ce(u−v)t
代入 t=0,1 可以确定 F=(u−v)e(u−v)tu−veu−v
接下来用 x 元计量边数，用 y 元计量大于号的数量。
对于 pk 的左侧，我们令 u=x,v=xy；对于右侧我们令 u=xy,v=x。那么 L=(1−y)ex(1−y)t1−yex(1−y)R=(1−y)ex(1−y)(1−t)1−yex(1−y)
接下来有两条路。
离散微积分
我们直接考虑提取其系数。
我们知道 ([xn1]L)([xn2R]) 就等于 1n1!n2!(1−y)n1+n2+2(∑j≥0yj(t+j)n1)(∑j≥0yj((j+1)−t)n2)
事实上在这个地方我们容易求出结果（关于 t 的多项式）在 0,1,…,n 处的点值，能否通过取决于插值的常数。
不过这个做法不太有趣，此处略过。
去掉常数 (−1)n2n1!n2!，我们把它变成 [ym](1−y)n+1∑i≥0∑j≥0yi+j(t+i)n1(t−(j+1))n2=m∑s=0[ym](1−y)n+1yss∑i=0(t+i)n1(t+i−(s+1))n2
我们将其拆成正方向的无穷求和加上一个差分 Δs+1f(t)=f(t)−f(t+s+1)。
设 fs=[ym](1−y)n+1ys。
m∑s=0fsΔs+1(∑i≥0(t+i)n1(t+i−(s+1))n2)
这个地方我们考虑把差分换到无穷求和里面，看起来我们求和的东西是不变的，但是实际上无穷求和各项的关系并不这么单纯，正像你作不定积分后会多出一个常数。
所以实际上变成了 m∑s=0fs(∑i≥0Δs+1(t+i)n1(t+i−(s+1))n2)+C
不管常数项，即 ∑i≥0(m∑s=0fs[(t+i)n1(t+i−(s+1))n2−(t+i+(s+1))n1(t+i)n2])
但是这个 C 一看就不像是人工分析可以搞出来的东西……
不过回到原先的概率密度函数，我们会发现令 f0 加上 C 会导致所有 ai 之和加上 C 倍的某个常数（而这个常数是容易算出的），而我们知道 ai 之和应当等于 ⟨nm⟩。
令 D 是求导算子，我们知道 f(t+c)=ecDf(t)，因而不妨设 F(x)=m∑s=0fsxs+1，就有 ∑i≥0((t+i)n1F(e−D)(t+i)n2−(t+i)n2F(eD)(t+i)n1)
我们知道我们作一次位移是 eD，正向差分是 1−eD，它的逆运算就是 11−eD，然后为了能够求逆我们恰好就凑出来了一个伯努利数的形式 ∫B(D)((t+i)n1F(e−D)(t+i)n2−(t+i)n2F(eD)(t+i)n1),B(t)=t1−et
接下来问题落在计算 G(x)。我们知道 F(x)=m∑i=0(n+1m−i)(−1)m−ixi+1
不妨设 F=xf，令 C=(n−m+1)f0=(n−m+1)(n+1m)(−1)m，那么我们知道 (n−m+1+i)fi=−(m−i+1)fi−1+[i=0]C(n−m+1)f+xf′=−mxf+x2f′+C
令 G(x)=F(ex)=exf(ex)=exg(x)，那么 (n−m+1)f(ex)+exf′(ex)=−mexf(ex)+e2xf′(ex)+C(n−m+1)g+g′=−mexg+exg′+C(n−m+1+mex)g+(1−ex)g′=C((n−m)e−x+m+1)G+(e−x−1)G′=C
提取 [xi] 得 (n−m)i∑j=1(−1)jj!Gi−j+(n+1)Gi+i∑j=1(−1)jj!(i−j+1)Gi−j+1=[i=0]C
整理得 (n−i+1)Gi=[i=0]C−(n−m)i−1∑j=0Gj(−1)i−j(i−j)!−i−1∑j=1jGj(−1)i−j+1(i−j+1)!
四元生成函数
我们先不提取系数，而是先综合考虑整体的生成函数。
左侧和右侧的 x 元分别用 p,q 代替，令 n1=k−1,n2=n−k，那么问题变为提取 [ympn1qn2](1−y)2ep(1−y)t+q(1−y)(1−t)(1−yep(1−y))(1−yeq(1−y))
对 p,q 换元，提出 (1−y)，则 (1−y)n+1ept+q(1−t)(1−yep)(1−yeq)
作部分分式，则 (1−y)n+1ept+q(1−t)1ep−eq(ep1−yep−eq1−yeq)
这看起来不太能计算，但是某些奇思妙想让我们试图对 t 求导， (1−y)n+1ept+q(1−t)p−qep−eq(ep1−yep−eq1−yeq)=(1−y)n+1ept+q(1−t)(p−q)e−qep−q−1(ep1−yep−eq1−yeq)=(1−y)n+1e(p−q)tB(p−q)(ep1−yep−eq1−yeq)
其中 B(x)=xex−1。
损失的常数可以使用上面提到的方法类似处理。
设 F(x)=∑i≥0[ym−i](1−y)n+1xi+1,G(x)=F(ex)，提取 ym 的系数 e(p−q)tB(p−q)(G(p)−G(q))
分别考虑 e(p−q)tB(p−q)G(p),e(p−q)tB(p−q)G(q)。
以前者为例，我们考虑换元：令 pr=q，则变为 ep(1−r)tB(p(1−r))G(p)
对其提取 pn−1rn2 的系数，有 [pn−1rn2]ep(1−r)tB(p(1−r))G(p)=∑j≥0([pj]B(p)ept)([rn2](1−r)j)([pn−1−j]G(p))
设 P(p)=∑j≥0pn−1−j([rn2](1−r)j)([pn−1−j]G(p))，那么 [pn−1]P(p)B(p)ept=∑j≥0tjj![pn−1−j]P(p)B(p)
类似地，设 Q(q)=∑j≥0qn−1−j([rn1](r−1)j)([qn−1−j]G(q))，就有 ∑j≥0tjj![qn−1−j]Q(q)B(q)
G 的求算已经在上文提到过。
时间复杂度 O(nlog2n) 或 O(nlog2nloglogn)。
代码：
1 |
|