| 不等数列 |
|
试题描述
|
|
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。 |
|
输入
|
|
第一行2个整数n,k。
|
|
输出
|
|
一个整数表示答案。
|
|
输入示例
|
|
5 2
|
|
输出示例
|
|
66
|
|
其他说明
|
|
对于30%的数据：n <= 10
对于100%的数据：k < n <= 1000， |
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int f[1010][1010]; 6 int main() 7 { 8 int n,k; 9 scanf("%d%d",&n,&k); 10 for(int i=1;i<=n;i++) f[i][0]=1; 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=k;j++) 13 { 14 f[i][j]=f[i-1][j-1]*(i-j)+f[i-1][j]*(j+1); 15 f[i][j]%=2012; 16 } 17 printf("%d",f[n][k]); 18 }
原文：http://www.cnblogs.com/wls001/p/4992172.html
