首页 > 代码库 > 动态规划 洛谷P2401 不等数列
动态规划 洛谷P2401 不等数列
P2401 不等数列
题目描述
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2015取模。
注：1~n的排列指的是1~n这n个数各出现且仅出现一次的数列。
输入输出格式
输入格式：第一行2个整数n,k。
输出格式：一个整数表示答案。
输入输出样例
输入样例#1：
5 2
输出样例#1：
66
说明
对于30%的数据：n <= 10
对于100%的数据：k < n <= 1000
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,k,f[1010][1010]; 7 int main(){ 8 scanf("%d%d",&n,&k); 9 for(int i=1;i<=n;i++) f[i][0]=1; 10 for(int i=1;i<=n;i++) 11 for(int j=1;j<=k;j++){ 12 f[i][j]=((f[i-1][j]*(j+1))%2015)+((f[i-1][j-1]*(i-j)%2015)); 13 f[i][j]=f[i][j]%2015; 14 } 15 printf("%d",f[n][k]); 16 return 0; 17 }
动态规划 洛谷P2401 不等数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。