YZOJ P3129 [校内训练20170627]跳格子

时间限制：1000MS 内存限制：524288KB

难度：\(7.0\)

• 题目描述

在一个花园里有一排 \(n\) 个格子，这些格子编号为 \(1\) 到 \(n\) 。袋鼠喜欢在花园的格子上跳跃。

袋鼠的跳跃方式是这样的：一开始，袋鼠位于 \(s\) 号格子上，接着它会选择一个尚未经过的格子上跳跃，经过 \(n-1\) 次跳跃后，所有格子都被经过了一次，袋鼠的跳跃将结束。袋鼠总是会在 \(t\) 号格子结束跳跃。

由于袋鼠中了病毒，所以如果上一步往前跳，那么这一步必须往后跳；反之，若上一步往后跳，那么这一步往前跳。

请问袋鼠有多少种跳跃的方案呢？

形式化地，你需要求出有多少个 \(1\) 到 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\)，满足：

1， \(p_1=s ，p_n=t\)；

2， 对任意 \(2 \leq i \leq n-1\)，或者 \((p_i-1<p_i) \land (p_i+1<p_i)\) ，或者 \((p_i-1>p_i) \land (p_i+1>p_i)\) 。

• 输入格式

输入共一行，包含三个正整数 \(n, s, t\) 。

• 输出格式

输出共一行，包含一个整数，表示跳跃的方案数对 \(1,000,000,007\) 取模的结果。

• 样例输入【包含两组样例】

• 样例输出

• 样例 1 说明

从 \(2\) 号格子到 \(3\) 号格子的跳跃方案有两种，一种是 \(2,1,4,3\)，一种是 \(2,4,1,3\) 。

• 数据规模与约定

 

 

 

---

 

 

 

考场上疯狂打表找规律，然后还没找出来，调试代码没删，所以就爆了零。

听说本题有数学解，但是我太菜我不会我想不出来，这里是Wiki 的说明。

 

本题运用 接头DP 的方法统计方案数（接头DP？？？我也是第一次听说），即在DP的时候考虑当前格子和它的上一个及下一个格子（若存在）的连接情况。

记 o- 表示 从这个格子出发向右 或者 从右边到达这个格子结束，-o 表示 从这个格子出发向左 或者 从左边到达这个格子结束；>o 表示 从左边进入这个格子再从左边出去，o< 表示 从右边进入这个格子再从右边出去。（注意，由于题目的特殊限制，所以只有这四种情况）

那么对于第一个格子，因为它左边已经没有格子，所以它的接头只有两种情况。

1， 若 \((s = 1) \lor (t = 1)\) ，那么它只可能是 o- 这种情况。

2， 若 \((s \ne 1) \land (t \ne 1)\) ，那么它只可能是 o< 这种情况。

同样，对于第 \(n\) 个格子，它右边已经没有格子，所以它的接头也只有两种情况。

1， 若 \((s = n) \lor (t = n)\) ，那么它只可能是 -o 这种情况。

2， 若 \((s \ne n) \land (t \ne n)\) ，那么它只可能是 >o 这种情况。

那么对于其他的非 \(1\) 非 \(n\) 的格子 \(i\)，它的接头也会有两种情况。

1，若 \((i = s) \lor (i = t)\)，那么它可能为 o- 或 -o 的其中一种情况。

2，若 \((i \ne s) \land (i \ne t)\)，那么它可能为 >o 或 o< 的其中一种情况。

例如样例 \(1\) 对应 o< -o o- >o 和 o< o- -o >o 这两种连接情况。

注意到，连接的方向可能相同，但是连接的顺序可能不同，就如同上面的第 \(1\) 个格子，所以状态只有一维是不够的。

因此，设 \(f_{i, j}\) 为表示当前按顺序做到第 \(i\) 个格子，此时剩余的未配对的 o< 形连接还有 \(j\) 个的方案数。

考虑初始值，其实已经在上面有所涉及，即 \((s = 1) \lor (t = 1)\) 时 \(f_{1, 0}=1\) ，\((s \ne 1) \land (t \ne 1)\) 时 \(f_{1, 1}=1\) 。

考虑转移，假设当前做到第 \(i\) 个格子，同样有两种情况。

1，\((i = s) \lor (i = t)\) ，可能为 o- 或 -o 。若是 o- ，则它对未配对的 o< 形连接的个数没有影响；若是 -o ，则它需要选择前面的一个未配对的 o< 进行接头配对。即 \(f_{i, j}=f_{i-1, j}+\left( j+1 \right) \cdot f_{i-1, j+1}\) 。

2，\((i \ne s) \land (i \ne t)\)，可能为 >o 或 o< 。若是 >o，则它可以选择之前任意两个未配对的 o< 并把它们连在一起，或者是连接从 \(s\) 或 \(t\) 出来的一条链（注意，仅当 \(i>s\) 或 \(i>t\) 时才能进行连接）；若是 o<，则它仅仅只是增加了一个未配对的 o< 。即 \(f_{i, j}=f_{i-1, j-1}+j(j+1) \cdot f_{i-1, j+1} + [i>s]f_{i-1, j+1}+[i>t]f_{i-1, j+1}\) ，化简得 \(f_{i, j}=f_{i-1, j-1}+(j+1)(j+[i>s]+[i>t]) \cdot f_{i-1, j+1}\) 。

由于全部做完一定不会剩下未配对的 o< 形连接，而不论是哪种情况一定不改变未配对的 o< 形连接的数量，答案即为 \(f_{n, 0}=f_{n-1, 0}\) 。

这样的时间复杂度为 \(O(n^2)\) 。