HDU1799循环多少次？

蔚落 2022-05-23 06:51 178阅读 0赞

# 循环多少次？ #

**Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 5819 Accepted Submission(s): 2237**

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有总共多少计算量。

Input

有T组case，T<=10000。每个case有两个整数m和n，0<m<=2000，0<n<=2000.

Output

对于每个case，输出一个值，表示总的计算量，也许这个数字很大，那么你只需要输出除1007留下的余数即可。

Sample Input

2 1 3 2 3

Sample Output

3 3

注意观察到，可以发现循环的值是；C(n,m)=n!/(m!\*(n-m)!)，因为n值过大，不可以直接用公式

组合数学的递推公式：C(n,m)=C(n,m-1)+C(n-1,m-1)

看了答案才知道是C\[m\]\[n\]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=2000+5;
    const int c=1007;
    int a[maxn][maxn];
    int main()
    {
    	memset(a,0,sizeof(a));
    	for(int i=1;i<maxn;i++)
    	{
    		a[i][i]=1;
    		a[i][0]=1;
    	}
    	for(int i=2;i<maxn;i++)
    		for(int j=1;j<maxn;j++)
    			a[i][j]=a[i-1][j-1]%c+a[i-1][j]%c;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int n,m;
    		scanf("%d %d",&n,&m);
    		printf("%d\n",a[m][n]%c);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关外层循环6次，每次内层只循环1次

这是一个使用两层循环的程序，外层循环6次，内层循环1次。具体的代码如下： for i in range(6): 外层循环6次 for j in r

布满荆棘的人生/ 2024年03月25日 16:29/ 0 赞/ 45 阅读

相关 php 每小时执行多少次

session\_start(); /\\ \ 每小时执行多少次 \/ function everyHour()\{ $h = date('H');

心已赠人/ 2022年08月26日 00:53/ 0 赞/ 171 阅读

相关 ZZULIOJ 1799: wrz的压岁钱【数学】

1799: wrz的压岁钱 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 394 Solved: 66 [

系统管理员/ 2022年08月18日 10:59/ 0 赞/ 138 阅读

相关子线程循环10次,紧接着主线程循环100次，来回50次

package cn.test.thread; / 子线程10次，主线程100次，来回50次 / public clas

ゝ一世哀愁。/ 2022年08月08日 06:44/ 0 赞/ 104 阅读

相关 java多线程：子线程循环10次，主线程接着循环100次，如此循环50次

package com.view04.alternate.print; / 子线程循环10次，主线程接着循环100次，如此循环50次的问题 @au

淡淡的烟草味﹌/ 2022年06月18日 07:51/ 0 赞/ 161 阅读

相关 HDU 1799

循环多少次？ Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/3

妖狐艹你老母/ 2022年06月16日 01:17/ 0 赞/ 89 阅读

相关子线程循环10次，主线程循环100次，如此循环100次

package thread; / 一、使用wait、notify 子线程循环10次，主线程循环100次，如此循环100次。 / publ

小灰灰/ 2022年05月29日 01:00/ 0 赞/ 175 阅读

相关 HDU1799循环多少次？

循环多少次？ Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

蔚落/ 2022年05月23日 06:51/ 0 赞/ 179 阅读

相关 [work] shell循环100次

前言用bash shell写程序时，经常会用到for循环，特别是从1到100这种需求，这里记录几种shell中从1到100的循环方法方法类c语言 for (

ゝ一纸荒年。/ 2022年05月10日 13:03/ 0 赞/ 252 阅读

相关 bzoj1799 self 同类分布（数位dp）

题意：给出a,b，求出\[a,b\]中各位数字之和能整除原数的数的个数。分析：一个数的数字和是很小的，最大为9\18，那么我们可以枚举这个数位和，因为这个数位和是要作

迈不过友情╰/ 2021年11月29日 13:48/ 0 赞/ 188 阅读