首页 > 其他 > 详细

不等数列(noip 2014 模拟题)

时间:2016-06-19 21:14:26      阅读:145      评论:0      收藏:0      [点我收藏+]

【题目描述】

将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2012取模。

 

【输入格式】

第一行2个整数n,k。

 

【输出格式】

一个整数表示答案。

 

【样例输入】

5 2

【样例输出】

66

【数据范围】

对于30%的数据:n <= 10

对于100%的数据:k < n <= 1000,

 

技术分享
/*
  f[i][j]向前i位数中插入j个‘<’种数
      当我们向长为i-1序列中插入第i个数时,当插入一个‘<‘中或序列左端时,
  ‘<‘数量不变,‘>‘数量+1,且可以插入的位置有j+1个;当插入一个‘>‘中或
  序列右端时,‘>‘数量不变,‘<‘数量+1,且可以插入的位置有i-j个。
      可得递推公式:
          f[i][j]=f[i-1][j]*(j+1)+f[i-1][j-1]*(i-j) 
*/
#include<cstdio>
#include<iostream>
#define M 1010
using namespace std;
int f[M][M];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
      f[i][0]=1;
    for(int i=2;i<=n;i++)
      for(int j=1;j<=i-1;j++)
      {
          f[i][j]=f[i-1][j]*(j+1)+f[i-1][j-1]*(i-j);
          f[i][j]%=2012;
      }
       
    printf("%d",f[n][k]);
    return 0;
}
View Code

 

不等数列(noip 2014 模拟题)

原文:http://www.cnblogs.com/harden/p/5598695.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!