POJ 1277

题目描述-戳我跳转

如果两个数之间的所有数(可以为$0$个)小于这两个数的对称为好对 求有多少个$n$个数的全排列的好对个数正好为$m$(对$9937$取模)

这道题求全排列个数,暴力可以想dfs,但想拿满分,数学方法或者dp 纯数学好像没思路,有的话在下面留言探讨

解法-DFS

枚举全排列,求好对个数,检验一下即可 另外可以用全排列展开尝试一下

解法-计数dp

对于全排列而言,我们可以用增添法,对于排好的数列,下一个数字可以插入到里面

当然我们希望能够差入最小的,这样我们就不需要考虑和别的凑成好对了,因为他只会与旁边的凑成好对

这样就出来了,$dp_{i,j}$表示$i$个人$j$个好对的方案数

转移方程需讨论:

1. 新插入的在边上-$dp_{i,j}=dp_{i-1,j-1} \times 2$
2. 新插入的在中间-$dp_{i,j}=dp_{i-1,j-2} \times (i-2)$

最后记得取模

当然我还挂在了一点 就是要判断$j$的大小 $j=1$只进行转移$1$ $j>=2$转移$1,2$

记住初值$dp_{1,0}=1$