[TIL]二項係数

にこうけいすう
この項係数を処理する前に,この項の定理を根本的に理解しなければならない.
この定理は(A+B)^n(ここではnは音ではなく整数)が多項式を展開する際に用いられる定理であり,ここで「この項」という言葉は「二つの項」を意味する.
この係数は、(A+B)^nが多項式を展開するときの、A^r*B^(n-r)(0<=r<=nの整数)の係数を表します.
a^r*b^(n−r)の係数は、任意に配列されたn文字の総数に等しく、組合せに等しい.
したがって、A^r*B^(n−r)の係数はncrに等しい.
これらの項係数の数学的証明または性質を詳細に論じないが,PSにこれらの項係数に関連する問題が発生した場合,
この係数を迅速かつ効率的に求める方法に重点を置いた.
この係数PSを2つの問題によって理解してみよう.まず最も基礎的な二項係数を求める問題である.
自然数Nと整数Kが与えられると、この係数が10007のモード演算値が求められる.(1 <= N <= 1,000/0 <= K <= N)

binomial_coefficient(N, K){
	K = Max(K, N-K); // K와 N-K 중 큰 수를 고른다. return으로  K를 나눈 값을 return하는데 K가 0일 수 있기 때문에
	A = N;
	
	for(i = K-1; i > 0; i--){
		A = A * (N - i); // nPk
		K = K * i;	// k!
	}
	
	return A/K; //nPk/k! == nCk
}

通常、上記の問題は表面的にはreturn値が非常に大きく、オーバーフローが発生する可能性があるため、便宜上、10007を除いた残り値を求める問題と考えられる.
また,実際にはNの範囲は1000であるので,この係数を固定的に求め,そのままダイラ演算に戻すことができる.
Nの範囲が400000なら、上記のようにできますか?同一の自然数Nと整数Kを与えた場合,この係数を求める問題.
Nの範囲を40,000,000に拡張し,この係数が10,000,000,000の乗算値を求める.
この場合,第1の問題とは異なり,モジュール化演算の存在の有無が重要となる.
この問題を解決するために,我々は前に学習したモジュール,演算の分配法則属性を利用しなければならない.
NとKの二項係数はnCk=N!/(K!*(N-K)!) いいですよ.
では、この係数を型乗演算に分割して求めることはできるだろうか.
しかし、上から見ると、加算、減算、乗算については、分配法則は存在するが、除算は存在しない.
すなわち(A/B)mod M!=(A mod M)/(B mod M)mod M.
ここでAはN!BはK!*(N-K)! 代入してみます.
(N!/K!(N-K)!) mod M != ((N! mod M)/(K!(N-K)! mod M))はmod Mに変更できます.
なぜ設立すらできないのか、面倒に大学に代入し、儀式に原因があることを自分の目で確認した.
私たちのこの項係数の点数は除算なので分配法則は適用されず,この点数を乗算に捻じ曲げると,この項係数の分配法則を可能にすることができる.
では、乗算はどのように生成されるのでしょうか.点数を乗算に変える方法は、力源を利用すると簡単にできます.
A/B=Cの場合、A*B^(-1)=Cとなります.すなわち、AをBで除算することは、AにBを乗じた逆元に等しい.
だから(N!/K!(N-K)!)modmは(N!(K!*(N-K)!)^(-1))modmで表すことができます.
力源を用いて除算を乗算に成功した.しかし除法が存在するのは点数のためで、点数の逆原は点数ではありませんか?
この問題を解決するために必要な公式は「フェルマの小さな定理」である.
フェルマの小さな整理は以下の通りです.
Aは整数、Pは小数、AはPに分けない場合(AはPの倍数ではない)
A ^P≡A(mod P).(Pについては、モジュール化された連合です.Pの残りの部分を除いて同じです.)
これはこのように表現できる->A^P mod M≡A mod M
すなわち,上記の式がどのように証明されるかに興味を持たず,証明された式をどのように使用するかに興味を持つエンジニアたちである.
上記式を再適用すると、^(P−1)≡1(modP)=>A*A.(P−2)≡1(modP)に変換することができる.
驚くべきことに、A(modP)に対する逆源はA^(P−2)(modP)である.
問題に戻ってフェルマの小さな定理でこの点数の力源を解くと
Aは(K!*(N-K)!)、Pは100000007に代入可能である.
A^(-1) = A^(P-2) = (K! (N-K)!)^(-1) = (K! (N-K)!)^10000005に達します.
ドメインメタはスコアではなく整数であり,モジュール乗算分配法則を適用できるようになった.
最終エクスポート式は次のとおりです.
N!/(K!(N-K)!) mod M
= (N! (K!(N-K)!)^(-1)) mod M
= (N! (K!(N-K)!)^(M-2)) mod M
= ((N! mod M) (K! * (N-K)!)^(M-2) mod M) mod M
こうして整理しておきました.
乗数分配法則を適用し,分割征服を行う.
分割征服は(K!*(N-K)!)^(M-2)では、指数M-2を引き続き半分に分け、指数が偶数の場合と奇数の場合を区別してリターンバックすればよい.
次は上記の問題の首都コードです.

// 수도코드
M = 1,000,000,007
A = factorial(N); // N!
B = factorial(K) * factorial(N-K) % M; // K!*(N-K)!

print(A * divide_conquer(B, M-2) % M); // (N! * (K!*(N-K)!)^(M-2)) mod M  

// 팩토리얼 구하면서 mod M을 계속 해줌
factorial(num){
	result = 1;
	while(num > 1){
		result = (result * num--) % M
	}
	
	return result;
}

// num : 밑수, exp : 지수
divide_conquer(num, exp){
    	if(exp == 1) return num % M; // 지수가 1일 경우 num^1 이므로 num % M 리턴
    	
	temp = divide_conquer(num, exp/2); // 모듈라 연산 곱셈 분배법칙을 이용한 분할 정복
	
	if(exp % 2 == 1) return (temp * temp) * num % M; // 분할 정복이 끝나고 지수가 홀수가 남으면 ex)A^5 = A^2 * A^2 * A
	else return temp * temp % M; // 지수가 짝수면 A^4 = A^2 * A^2
}