线性dp-计数类题目11(不等数列)

解题思路这道题我们定义f[i][j]f[i][j]f[i][j]为1至n1至n1至n的排列中有jjj个小于号的方案数。当j0j0j0时我们知道只有一种就是这个排列的数按从大到小排列。当i2,j1i2,j1i2,j1时f[i][j]f[i][j]f[i][j]可以从f[i−1][j−1]f[i-1][j-1]f[i−1][j−1]和f[i−1][j]f[i-1][j]f[i−1][j]转移过来当我们把数iii插入到1至i−11至i-11至i−1的排列时插在第一个数前面或者插在前小后大的两个数之间实际上小于号数量是没变的。插在最后一个数后面或者插在前大后小的两个数之间小于号数量会加一个。所以我们说f[i][j]f[i][j]f[i][j]可以从f[i−1][j−1]f[i-1][j-1]f[i−1][j−1]和f[i−1][j]f[i-1][j]f[i−1][j]转移过来。我们知道对于1至i−11至i-11至i−1的排列有iii个位置可以把数iii插进去如果原本有j−1j-1j−1个小于号,那就有i−1−1−(j−1)i-1-1-(j-1)i−1−1−(j−1)个大于号即i−j−1i-j-1i−j−1个大于号有i−j−1i-j-1i−j−1对前大后小的两个数这些都是可插入的位置再加上我们可以把数iii插到最后一个数后面所以可以得到状态转移方程f[i][j](f[i][j]f[i−1][j−1]∗(i−j))f[i][j](f[i][j]f[i-1][j-1]*(i-j))f[i][j](f[i][j]f[i−1][j−1]∗(i−j))。如果原本有jjj个小于号那就有jjj个可插入的位置再加上我们可以把数iii插到第一个数前面所以可以得到状态转移方程f[i][j](f[i][j]f[i−1][j]∗(j1))f[i][j](f[i][j]f[i-1][j]*(j1))f[i][j](f[i][j]f[i−1][j]∗(j1))。AC Code#includebits/stdc.husingnamespacestd;#defineintlonglongintn,k,f[1005][1005];signedmain(){cinnk;f[1][0]1;for(inti1;in-1;i){for(intj0;ji;j){f[i1][j](f[i1][j]f[i][j]*(j1)%2015)%2015;f[i1][j1](f[i1][j1]f[i][j]*(i-j)%2015)%2015;}}coutf[n][k];return0;}