LittleElephantAndPermutationDiv1

作者：何中天

关键字：dp

题目简述

对于两个排列a和b，定义magic(a,b) = max(a1,b1) + max(a2,b2) + ... + max(an,bn).

给定n和K，求有几对排列 pairs(a,b) 满足a和b的长度都为n，并且magic(a,b) >= k。 答案模1,000,000,007。

数据范围 n <= 50, K <= 2500

算法

我们发现可以先固定排列a为(1,2,...,n)，最后将答案乘以n!即可。

我们可以设计状态f[i][j][k]表示已经在b中填充了数1到i，填在下标为i+1到n的数有j个，满足max(a[p],b[p])<=i的max(a[p],b[p])的和为k，这样的的填充方法数。

于是可以分类：

将数i填在下标为i处，则k+=i，j不变.

将数i填在下标小于i处，下标为i处填入了小于i的数，则k+=2 * i， j--.

将数i填在下标小于i处，下标为i处填入了大于i的数，则k+=i，j不变.

将数i填在下标大于i处，下标为i处填入了大于i的数，则k不变，j++.

将数i填在下标大于i处，下标为i处填入了小于i的数，则k+=i，j不变.

最终答案为f[n][0][x]的和，其中x>=k.