企业官网建设流程全解析

解题思路

这道题我们定义f[i][j]f[i][j]f[i][j]为1至n1至n1至n的排列中有jjj个小于号的方案数。当j=0j=0j=0时，我们知道只有一种，就是这个排列的数按从大到小排列。当i>=2,j>=1i>=2,j>=1i>=2,j>=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]转移过来，当我们把数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]∗(j+1))f[i][j]=(f[i][j]+f[i-1][j]*(j+1))f[i][j]=(f[i][j]+f[i−1][j]∗(j+1))。

AC Code

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintn,k,f[1005][1005];signedmain(){cin>>n>>k;f[1][0]=1;for(inti=1;i<=n-1;i++){for(intj=0;j<i;j++){f[i+1][j]=(f[i+1][j]+f[i][j]*(j+1)%2015)%2015;f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(i-j)%2015)%2015;}}cout<<f[n][k];return0;}