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