hdoj 1799サイクルは何回ですか?
1523 ワード
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には2つの整数mとnがあり、0
Output
各caseについて、合計の計算量を表す値を出力します.この数字は大きいかもしれませんが、1007を除いた残りの数を出力するだけでいいです.
Sample Input
Sample Output
3
3
コード:
プログラミングでは,特にサイクルの部分について,時間的複雑さを考慮することがしばしば必要であることを知っている.たとえば、
コードに表示される場合
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には2つの整数mとnがあり、0
Output
各caseについて、合計の計算量を表す値を出力します.この数字は大きいかもしれませんが、1007を除いた残りの数を出力するだけでいいです.
Sample Input
2
1 3
2 3
Sample Output
3
3
コード:
#include<iostream>
using namespace std;
int c[2001][2001];
int main()
{
int i,j;
for(i=1;i<=2000;i++)
{
c[i][0]=1;
c[i][1]=i%1007;
}
for(i=2;i<=2000;i++)
{
for(j=2;j<=i;j++)
{
c[i][j]=(c[i-1][j]%1007+c[i-1][j-1]%1007)%1007;
}
}
int t,m,n;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d%d",&m,&n);
if(m>n){printf("0
");continue;}
else printf("%d
",c[n][m]);
}
}
return 0;
}