「NOIP模拟赛」不等数列
不等数列(num.cpp/c/pas)
「题目描述」
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。
「输入格式」
第一行2个整数n,k。
「输出格式」
一个整数表示答案。
「样例输入」
5 2
「样例输出」
66
「数据范围」
对于30%的数据：n <= 10
对于100%的数据：k < n <= 1000
题解
f[i][j]表示前i个j个小于号的方案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<iostream> #include<cstdio> using namespace std; int n,k;int f[1001][1001]; int main() { //freopen("num.in","r",stdin); //freopen("num.out","w",stdout); 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<=min(i-1,k);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]); //system("pause"); return 0; } |
Subscribe
计数器 9856460
OI 课件=>
OI 课件=>