（寒假集训）不等数列-白红宇

（寒假集训）不等数列

阅读量：6769 次

发布时间：2019-06-26

本文共 922 字，大约阅读时间需要 3 分钟。

不等数列

时间限制: 1 Sec 内存限制: 256 MB

提交: 9 解决: 9

[][][]

题目描述

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

输入

第一行2个整数n,k。

输出

一个整数表示答案。

样例输入

5 2

样例输出

提示

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

对于100%的数据：k < n <= 1000。

【分析】dp[i][j]表示 i 个数中有 j 个 <的方案数。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #define inf 2e9#define met(a,b) memset(a,b,sizeof a)typedef long long ll;using namespace std;const int N = 2e3+5;const int M = 4e5+5;int n,m,k,sum,ans;ll dp[N][N];int main(){ scanf("%d%d",&n,&k); dp[2][1]=1; for(int i=1;i<=n;i++)dp[i][0]=1; for(int i=3;i<=n;i++){ for(int j=1;j<=min(i-1,k);j++){ dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j))%2012; } } printf("%lld\n",dp[n][k]); return 0;}