发现只有200个人AC,于是开始做,一眼看过去,数据范围这么小一定是神题,然后分析了一发,发现下界为n-1,貌似上界也是O(n)级别的呀,怎么m<10000,一定是我想错了,感觉就是每一个人之和左边和右边第一个比他高的人说话,最多O(2*n)呀,然后打算写组合数,因为开始一个顺序的数列答案为n-1,然后每次交换不为最高位可以使答案加1,发现好麻烦,决定转战dp,fij,直接表示答案,递推,就是每次加一个比所有人都矮的人,有n-1各位置可以使答案加2,2各位置使答案加1,然后就rank前20了.......
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<ctime> #define mo 9937 using namespace std; int n,m; int f[101][211]; void pre() { for(int i=2;i<=80;i++) { for(int j=0;j<=200;j++) { f[i][j+1]=(f[i][j+1]+f[i-1][j]*2)%mo; f[i][j+2]=(f[i][j+2]+f[i-1][j]*(i-2))%mo; } } } int main() { f[1][0]=1; pre(); while(1) { scanf("%d %d",&n,&m); if(n==0 && m==0) break; if(m>200){printf("0 ");continue;} printf("%d ",f[n][m]); } return 0; }