题目：
仔细思考dp。
第一问，考虑已知 i-1 个数有多少种方案。再放入一个数，它是最大的且在最后面，所以它的位置不同的话，就是不同的方案。它在特定的位置，其余部分的值就是 i-1 的值。
所以再用前缀和优化成 n^2 即可。k可减任意个2。
第二问，还是像上面一样考虑。但新来的数只会和前面的数交换一次。任何一种交换 k ( k>1 ) 次的方案都可以转换成前面的数先交换 k-1 次，再由新来的数交换一次。所以就能很方便地dp了。
还可以从逆序对的角度考虑第一问、从斯特林数的角度考虑第二问。反正式子是一样的。
#include#include #include #include #define ll long longusing namespace std;const int N=3005,mod=1e9+7;int n,k,dp[2][N],c[2][N],ans,u,v;int main(){ scanf("%d%d",&n,&k); dp[1][0]=1; for(int i=0;i<=k;i++) c[1][i]=1; u=0;v=1; for(int i=2;i<=n;i++) { for(int j=0;j<=k;j++) { dp[u][j]=(c[v][j]-(j-i>=0?c[v][j-i]:0)+mod)%mod; c[u][j]=(dp[u][j]+(j?c[u][j-1]:0))%mod; } u=!u;v=!v; } for(int i=k;i>=0;i-=2) (ans+=dp[v][i])%=mod; printf("%d ",ans); ans=0; u=0;v=1; memset(dp[1],0,sizeof dp[1]); dp[1][0]=1; for(int i=2;i<=n;i++) { for(int j=0;j<=k;j++) dp[u][j]=(dp[v][j]+(j?(ll)dp[v][j-1]*(i-1)%mod:0))%mod; u=!u;v=!v; } for(int i=0;i<=k;i++) (ans+=dp[v][i])%=mod; printf("%d\n",ans); return 0;}