HDU——1799循环多少次(杨辉三角/动态规划/C(m,n)组合数)
2024-08-30 01:10:22
循环多少次?
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3747 Accepted Submission(s): 1424
Problem Description
我们知道,在编程中,我们时常需要考虑到时间复杂度,特别是对于循环的部分。例如,
如果代码中出现
for(i=1;i<=n;i++) OP ;
那么做了n次OP运算,如果代码中出现
fori=1;i<=n; i++)
for(j=i+1;j<=n; j++) OP;
那么做了n*(n-1)/2 次OP 操作。
现在给你已知有m层for循环操作,且每次for中变量的起始值是上一个变量的起始值+1(第一个变量的起始值是1),终止值都是一个输入的n,问最后OP有总共多少计算量。
如果代码中出现
for(i=1;i<=n;i++) OP ;
那么做了n次OP运算,如果代码中出现
fori=1;i<=n; i++)
for(j=i+1;j<=n; j++) OP;
那么做了n*(n-1)/2 次OP 操作。
现在给你已知有m层for循环操作,且每次for中变量的起始值是上一个变量的起始值+1(第一个变量的起始值是1),终止值都是一个输入的n,问最后OP有总共多少计算量。
Input
有T组case,T<=10000。每个case有两个整数m和n,0<m<=2000,0<n<=2000.
Output
对于每个case,输出一个值,表示总的计算量,也许这个数字很大,那么你只需要输出除1007留下的余数即可。
Sample Input
2
1 3
2 3
1 3
2 3
Sample Output
3
3
3
学习了,原来Cmn还可以这么写..
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
int list[2001][2001];
int main(void)
{
memset(list,0,sizeof(list));
int i,j;
for(i=1;i<=2000;i++)
{
list[i][0]=1;
list[i][1]=i%1007;
}
for(i=2;i<=2000;i++)
{
for(j=2;j<=i;j++)
{
list[i][j]=(list[i-1][j]%1007+list[i-1][j-1]%1007)%1007;
}
};
int m,n,t;
cin>>t;
while (t--)
{
cin>>m>>n;
if(m>n)
cout<<"0"<<endl;//m>n则没有可能
else
printf("%d\n",list[n][m]);
}
return 0;
}
最新文章
- xcode archive 一直是灰色的
- 求当前时间100天后的时间日期,格式化为xxxx年xx月xx日
- Delphi7 安装ICS,与简单使用
- 禁止 IOS 系统 数字 变超链 (自动识别为电话号码)
- zookeeper集群安装配置
- 获取枚举Description的Name
- Delphi中停靠技术的实现
- Try,Catch,Finally三块中如果有Return是怎么个运行顺序
- 纯静态界面中(html)中通过js调用dll中的方法从数据库中读取数据
- Intellij Error:Cannot build Artifact &#39;XXX:war exploded&#39; because it is included into a circular dependency
- Linux Mint 17一周使用体验
- JAVA之旅(三十三)——TCP传输,互相(伤害)传输,复制文件,上传图片,多并发上传,多并发登录
- 解决PHP乱码
- awesome资源包
- Eclipse使用相关配置
- iOS手机淘宝加入购物车动画分析
- L268 A terrifying look at the consequences of climate change
- 定时任务Job
- cqlsh 一个错误
- SQL 上线平台(内含全部完整资料)