还是可以想出来的题目 不过考场上没有想出来 要 引以为戒。
初看觉得有点不可做 10分给到了爆搜。
考虑第一个特殊情况 B排列为1~m.
容易发现A排列中前m个数字 他们之间不能产生交换 且 第k个数字要交换到后面的m+1~n这些数字的时候 k~m的数字都要进行交换才行。
那么直接枚举有多少个数字到后面了 组合数可以解决 考虑剩下的那些空位怎么办。
其实就是要求出 \(f_i\) 其表示满足题目条件的i个数的排列的个数.
考虑递推 容易发现\(f_0=1,f_1=1\) 对于\(f_i\)考虑第i个数字不换 那么为\(f_{i-1}\)换的话有i-1种方法 对应的方案为\((i-1)\cdot f_{i-2}\)
综上可以得到\(f_i=f_{i-1}+(i-1)\cdot f_{i-2}\)
这样结合上面的dfs就可以获得30分了。
考虑另外一种递推的模型 可以发现m在第一个 那么就要想办法将m换到第一个。
显然 m可以不动 那么剩下的m-1个数字就要放到后面了。
m可以直接和1交换 那么剩下的m-2个数字要放到后面。
m还可以和后面的进行交换 其实就是m个数字放到后面。
三种情况分别讨论即可。结合上面的两种方法就可以得到50分了。具体细节看代码。
上午也只推到这里。因为感觉正解比较难 所以就每有一直探索下去 其实可以继续走下去。
考虑正解：综上其实可以发现 m个数全部扔到后面是一定合法的，那么其实就是考虑有多少个数字可以被扔到前面。
如果有k个数字在后面 那么前面这s=m-k个数字就应该在前面 且他们不能和后面的k个数字存在交换。
这样就要求他们是一个合法排列 容易想到合法情况最多只有一种 这点容易证明。
也就是说此时只需要判断s个数字放到前面是否合法 即满足题目中的条件。
可以暴力安排位置 因为第一个要放到数值最小的位置上去 这样暴力放然后再check即可。
复杂度\(m^2+n\)