1R/2016 07 12 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 16:		Line 16:
	#pragma warning(disable:4996)		#pragma warning(disable:4996)

	ULL fctrl[2000003];		ULL fctrl[2000003];

	void clearFctrl() {		void clearFctrl() {
Line 22:		Line 22:
	for (i = 0; i < 2000003; i++) {		for (i = 0; i < 2000003; i++) {
	if (i) {		if (i) {
	fctrl[i] = (fctrl[i - 1] * i) % T;		fctrl[i] = (fctrl[i - 1] * i) % T;
	}		}
	else fctrl[i] = 1;		else fctrl[i] = 1;
	}		}
	}		}
Line 34:		Line 34:
	ULL p;		ULL p;

	A = fctrl[n];		A = fctrl[n];
	B = (fctrl[k] * fctrl[n - k] )%T;		B = (fctrl[k] * fctrl[n - k] )%T;

	p = T-2;		p = T-2;
Line 96:		Line 96:
	== 15이원준 ==		== 15이원준 ==
	* 수알못이라 포기합니다...ㅠ		* 수알못이라 포기합니다...ㅠ

175.124.46.8 at 15:14, 12 July 2016

2016-07-12T15:14:32Z

← Older revision		Revision as of 15:14, 12 July 2016
Line 93:		Line 93:
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

			== 15이원준 ==
			* 수알못이라 포기합니다...ㅠ

175.124.46.8 at 15:14, 12 July 2016

2016-07-12T15:14:05Z

← Older revision		Revision as of 15:14, 12 July 2016
Line 5:		Line 5:
	= 참가자 =		= 참가자 =
	* 황창재		* 황창재
			* 15이원준
	= 코드 =		= 코드 =
	== 황창재 ==		== 황창재 ==

imported>황창재 at 07:12, 12 July 2016

2016-07-12T07:12:54Z

← Older revision		Revision as of 07:12, 12 July 2016
Line 89:		Line 89:
	** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리 ( A! == n! , B! == r!(n-r)! )		** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리 ( A! == n! , B! == r!(n-r)! )
	x^(p-1) mod p == 1 mod p 를 이용하여		x^(p-1) mod p == 1 mod p 를 이용하여
	A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함.		A x B^(p-2) mod p == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함.
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

imported>황창재 at 07:12, 12 July 2016

2016-07-12T07:12:33Z

← Older revision		Revision as of 07:12, 12 July 2016
Line 87:		Line 87:
	* nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함		* nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함
	* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.		* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.
	** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리		** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리 ( A! == n! , B! == r!(n-r)! )
	x^(p-1) mod p == 1 mod p 를 이용하여		x^(p-1) mod p == 1 mod p 를 이용하여
	A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ~~( A! == n! , B! == r!(n-r)! )~~		A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함.
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

imported>황창재 at 07:11, 12 July 2016

2016-07-12T07:11:57Z

← Older revision		Revision as of 07:11, 12 July 2016
Line 88:		Line 88:
	* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.		* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.
	** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리		** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리
	x^(p-1) mod p == 1 mod p 를 이용하여		x^(p-1) mod p == 1 mod p 를 이용하여
	A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )		A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

imported>황창재 at 07:11, 12 July 2016

2016-07-12T07:11:50Z

← Older revision		Revision as of 07:11, 12 July 2016
Line 88:		Line 88:
	* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.		* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.
	** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리		** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리
	x^(p-1) mod p == 1 mod p 를 이용하여		x^(p-1) mod p == 1 mod p 를 이용하여
	A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )		A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

imported>황창재 at 07:11, 12 July 2016

2016-07-12T07:11:41Z

← Older revision		Revision as of 07:11, 12 July 2016
Line 87:		Line 87:
	* nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함		* nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함
	* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.		* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.
	~~: >~~ 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리		** 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리
	x^(p-1) mod p == 1 mod p 를 이용하여		x^(p-1) mod p == 1 mod p 를 이용하여
	A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )		A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )
	* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.		* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
	* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.		* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

imported>황창재: {CREATE}

2016-07-12T07:11:09Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.codeground.org/practice/practiceProbView.do?probId=5|이항계수의 합]
= 참가자 =
* 황창재
= 코드 =
== 황창재 ==
// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <stdio.h>

typedef unsigned long long ULL;
#define T 1000000007

#pragma warning(disable:4996)

ULL fctrl[2000003];

void clearFctrl() {
int i;
for (i = 0; i < 2000003; i++) {
if (i) {
fctrl[i] = (fctrl[i - 1] * i) % T;
}
else fctrl[i] = 1;
}
}

ULL getC(ULL n, ULL k) {
ULL i;
ULL product;
ULL A, B;
ULL p;

A = fctrl[n];
B = (fctrl[k] * fctrl[n - k] )%T;

p = T-2;
while (p != 1) {
if (p % 2) {
A = (A*B) % T;
}
B = (B*B) % T;
p = p / 2;
}
product = (A*B) % T;

return product;
}

int main(void) {
/* 아래 freopen 함수는 input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 input.txt 로 부터 읽어오겠다는 의미의 코드입니다.
만약 본인 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면
그 아래에서 scanf 함수를 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */
// freopen("input.txt", "r", stdin);

setbuf(stdout, NULL);

int TC;
int test_case;

ULL sum;

ULL N, M;

clearFctrl();

scanf("%d", &TC);
for (test_case = 1; test_case <= TC; test_case++) {
// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
scanf("%d %d", &N, &M);

sum = getC(N + M + 2, M + 1) - 1;

// 이 부분에서 정답을 출력하십시오.
printf("Case #%d\n", test_case);
printf("%llu\n", sum);
}

return 0; // 정상종료 시 반드시 0을 리턴해야 합니다.
}

= 아이디어 =
== 황창재 ==
* nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함
* nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함.
: > 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리
x^(p-1) mod p == 1 mod p 를 이용하여
A x B^(p-2) == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. ( A! == n! , B! == r!(n-r)! )
* 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
* 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.