محاسبه‌ی ترکیب r از n

نویسنده: ATofighi
ارسال‌شده در:
دیدگاه‌ها: 0

بسم الله الرحمن الرحیم

در کانال تلگرامی @dore_com سعی شده تا برخی از نکات مورد نیاز برای مرحله ۳ گفته شود. یکی از این نکات محاسبه‌ی مقدار \(\left( \begin{array}{c} n \\ r \end{array} \right) mod \space m\) است که چون مطلب طولانی بود. اینجا می‌نویسمش.

اول از همه از همه التماس دعا در این شب مبارک رو دارم. امیدوارم موفق باشید.

برای خواندن مطلب به ادامه‌ی مطلب بروید.

محاسبه با کمک اتحاد پاسکال

این الگوریتم کد ساده‌ای دارد و از می‌توانید مطمئن باشید برای \(m\)های مختلف، پاسخ درستی به دست می‌آورید.

در اتحاد پارسکال داریم: \(\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}\) است. همچنین \(\binom{n}{0} = 1\) است. از این ایده و با کمک داینامیک می‌توان مقدار \(\binom{n}{r}\) را محاسبه نمود.

کد:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

const int N = 1000+17;
int C[N][N];
int m = 1e9+7;

int main()
{
    for (int i = 0; i < N; i++)
        C[i][0] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j-1]+C[i-1][j])%m;
}

که در این کد می‌تونید با استفاده از \(C[n][r]\) مقدار \(\binom{n}{r} mod \space m\) رو در بیارید.

این الگوریتم ابتدا زمان و مموری \(O(n^2)\) مصرف می‌کنه و هر انتخاب رو در \(O(1)\) پاسخ می‌ده.

محاسبه به کمک تجزیه

یکی از راه‌های محاسبه انتخاب، تجزیه‌ی فاکتوریل به عوامل اولش هست. برای این منظور از دو فکت مهم زیر استفاده می‌کنیم:

  • اگر \(p\) عددی اول باشد، توان \(p\) در تجزیه‌ی \(n!\) برابر است با: \(\sum_{i=1}^\infty {\left\lfloor \frac{n}{p^i} \right\rfloor}\).
  • \(\binom{n}{r} = {n! \over r!(n-r)!}\)

پس اگر اعداد اول ۱ تا \(n\) را محاسبه کنیم. می‌توان مقدار \(\binom{n}{r}\) را نیز محاسبه نمود.

کد:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6+17;
int m = 1e9+7;

/*
 * power function
 * @return a^b % mod
 * more details in https://telegram.me/dore_com/174
 */
int power(ll a, int b, ll mod = m)
{
	if (b == 0)
		return 1%mod;
	ll p = power(a, b>>1);
	p *= p;
	p %= mod;
	if (b & 1) {
		p *= a;
		p %= mod;
	}
	return p;
}

vector<int> primes;
bool prime[N];

inline int calcCSum(int n, int p)
{
	ll ans = 0, a = p;
	while(a <= n) {
		ans += n/a;
		a *= p;
	}
	return ans;
}

int C(int n, int r)
{
	if(r < 0 || r > n)
		return 0;
	if(r == 0)
		return 1;
	int ans = 1;
	for(int p: primes) {
		if(p > n) break;
		ans *= power(p, calcCSum(n, p)-calcCSum(r, p)-calcCSum(n-r, p), m);
		ans %= m;
	}
	return ans;
}

int main()
{
	// gharbal:
	fill(prime, prime+N, true);
	prime[1] = false;
	for (int i = 1; i < N; i++)
		if (prime[i]) {
			primes.push_back(i);
			for(int j = i+i; j < N; j += i)
				prime[j] = false;
		}

}

در این کد برای به دست آوردن اعداد اول از الگوریتم غربال استفاده شده همچین از تابع power که آموزش آن در کانال تلگرام است استفاده شده‌است. همچنین تابع calcCSum مقدار سیگما در فکت ۱ را محاسبه کرده و تابع \(C(n, r)\) مقدار \(\binom{n}{r}\) را محاسبه می‌کند.

این الگوریتم در ابتدا زمان \(O(n \lg\lg n)\) برای محاسبه‌ی غربال اراتستن و حافظه‌ی \(O(n)\) مصرف می‌کند. همچنین از ترکیب را در زمان \(O(n)\) پاسخ می‌دهد.

پس برای وقتی تعداد ترکیب‌های مورد نیاز برای محاسبه کم است و همچنین \(n\) عدد کوچکی است، این روش به صرفه‌ست.

محاسبه انتخاب وقتی n بسیار بزرگ و r بسیار کوچک است.

برای محاسبه‌ی این، اگر m عددی اول و بزرگتر از r بود می‌توان با کمک فرما مسئله را حل کرد. در غیر اینصورت با کمک تجزیه مسئله قابل حل است که در این بند به توضیح آن می‌پردازیم:

چون \(\binom{n}{r} = {n! \over r!(n-r)!} = {(n-r+1)\times(n-r+2)\times...\times n \over 2 \times 3 \times 4 \times ... \times r }\) است. می‌توانیم به ازای هر x از بالا و پایین را تجزیه کرده و به این روش مسئله را حل کنیم.

در این روش چون n فرض شده بسیار بزرگ است. تجزیه را در \(O(\sqrt n)\) انجام می‌دهیم. کد:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int m = 1e9+7;

/*
 * power function
 * @return a^b % mod
 * more details in https://telegram.me/dore_com/174
 */
int power(ll a, int b, ll mod = m)
{
	if (b == 0)
		return 1%mod;
	ll p = power(a%mod, b>>1);
	p *= p;
	p %= mod;
	if (b & 1) {
		p *= a;
		p %= mod;
	}
	return p;
}

vector<ll> getFactors(ll n)
{
	ll p = 2;
	vector<ll> res;
	while(p*p <= n) {
		while(n % p == 0) {
			res.push_back(p);
			n /= p;
		}
		p++;
	}
	if(n > 1) {
		res.push_back(n);
	}
	return res;
}


int C(ll n, int r)
{
	if(r < 0 || r > n)
		return 0;
	if(r == 0)
		return 1;
	if(n-r < r)
		r = n-r;

	map<ll, int> tajziye;

	for(ll i = n-r+1; i <= n; i++) {
		vector<ll> factors = getFactors(i);
		for(ll p: factors) {
			tajziye[p]++;
		}
	}
	for(ll i = 2; i <= r; i++) {
		vector<ll> factors = getFactors(i);
		for(ll p: factors) {
			tajziye[p]--;
		}
	}
	ll ans = 1;
	for(auto x: tajziye) {
		ans *= power(x.first, x.second);
		ans %= m;
	}
	return ans;
}

int main()
{

}

که در این کد تابع \(getFactors(n)\) عوامل اول عدد \(n\) را در زمان \(O(\sqrt n)\) محاسبه می‌کند و تابع \(C(n, r)\) نیز مقدار \(\binom{n}{r} mod \space m\) را محاسبه می‌کند.

این الگوریتم در هر بار اجرا مقدار \(O(r)\) حافظه نیاز دارد و همچنین در زمان \(O(r\sqrt n \lg r)\) طول می‌کشد. (در این پیاده‌سازی البته)

محاسبه به کمک قضیه‌ی کوچک فرما

اگر \(m\) اول بود و \(r, n-r < m\) می‌توان از این روش استفاده کرد.

در قضیه‌ی کوچک فرما گفته می‌شود که اگر \(m\) عددی اول باشد و \(a\) عددی باشد که بر \(m\) بخش پذیر نیست، \(a^{m-1} mod \space m = 1\) از این قضیه نتیجه می‌گیریم که \(a^{m-2} \equiv \frac{1}{a} \pmod m\) که کمک بزرگی در حل این مسئله می‌کند.

فرض کنید \(f[n] = n! \bmod m\)، در این صورت \(\binom{n}{r} \equiv \frac{n!}{r!(n-r)!} \equiv \frac{f[n]}{f[r]\times f[n-r]} \equiv f[n] \times (f[r]\times f[n-r])^{m-2} \pmod m\) .

پس کد زیر برای این روش است:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int m = 1e9+7;

/*
 * power function
 * @return a^b % mod
 * more details in https://telegram.me/dore_com/174
 */
int power(ll a, int b, ll mod = m)
{
	if (b == 0)
		return 1%mod;
	ll p = power(a%mod, b>>1);
	p *= p;
	p %= mod;
	if (b & 1) {
		p *= a;
		p %= mod;
	}
	return p;
}

const int N = 1e6+17;
ll f[N];

int C(ll n, int r)
{
	if(r < 0 || r > n)
		return 0;
	if(r == 0)
		return 1;
	return f[n]*power(f[r]*f[n-r]%m, m-2)%m;
}

int main()
{
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = (f[i-1]*i)%m;
	
}

که این کد نیاز به حافظه‌ی \(O(n)\) داشته و در ابتدا در زمان \(O(n)\) پردازش اولیه انجام می‌دهد. اما هر انتخاب را در \(O(\lg m)\) پاسخ می‌دهد.

همچنین اگر n بزرگ بود، می‌توان از ایده‌ی بخش قبل کمک گرفت و مقدار \(((n-r+1)\times(n-r+2)\times ... \times n)\times (f[r]^{m-2})\) را محاسبه کرد که حافظه و پردازش اولیه به \(O(r)\) کاهش یافته اما هر انتخاب در \(O(r)\) پاسخ داده می‌شود.

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int m = 1e9+7;

/*
 * power function
 * @return a^b % mod
 * more details in https://telegram.me/dore_com/174
 */
int power(ll a, int b, ll mod = m)
{
	if (b == 0)
		return 1%mod;
	ll p = power(a%mod, b>>1);
	p *= p;
	p %= mod;
	if (b & 1) {
		p *= a;
		p %= mod;
	}
	return p;
}

const int N = 1e6+17;
ll f[N];

int C(ll n, int r)
{
	if(r < 0 || r > n)
		return 0;
	if(r == 0)
		return 1;
	if(n-r < r) r = n-r;
	ll k = 1;
	for(ll i = n-r+1; i <= n; i++)
		k = k*(i%m)%m;
	return k*power(f[r], m-2)%m;
}

int main()
{
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = (f[i-1]*i)%m;
	
}

 

قضیه‌ی لوکا

باسپاس از آقای گرزی که این رو یادآوری کردند به من که اضافه‌ش کنم! ^_^

اطلاعات درباره‌ی این قضیه: https://en.wikipedia.org/wiki/Lucas%27_theorem

در بخش قبل یاد گرفتیم که چگونه وقتی \(m\) اول است و \(n, r < m\) هست، مقدار ترکیب رو حساب کنیم. حالا می‌خواهیم با کمک قضیه‌ی لوکا وقتی \(m\) اول است، بدون محدودیت اضافه مسئله را حل کنیم:

\(\binom{n}{r} \equiv \prod_{i=0}^{k}\binom{n_i}{r_i} \pmod m\)

که در آن

\(n = n_km^k +n_{k-1}m^{k-1}+...+n_1m + n_0 \\ r = r_km^k +r_{k-1}m^{k-1}+...+r_1m + r_0\)

که این با تغییری کوچک در کد قسمت قبل می‌توان \(O(m)\) در ابتدا برای محاسبه‌ی تابع f زمان و حافظه گرفت و با کمک تابع بازگشتی در \(O(log_m^n \times \lg m)\) مسئله را حل کرد.

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int m = 1827071;

/*
 * power function
 * @return a^b % mod
 * more details in https://telegram.me/dore_com/174
 */
int power(ll a, int b, ll mod = m)
{
	if (b == 0)
		return 1%mod;
	ll p = power(a%mod, b>>1);
	p *= p;
	p %= mod;
	if (b & 1) {
		p *= a;
		p %= mod;
	}
	return p;
}

const int N = 3e6+17;
ll f[N];

int C(ll n, int r)
{
	if(r < 0 || r > n)
		return 0;
	if(r == 0)
		return 1;
	if(n >= m) {
		return C(n%m, r%m)*C(n/m, r/m)%m;
	}
	return f[n]*power(f[r]*f[n-r]%m, m-2)%m;
}

int main()
{
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = (f[i-1]*i)%m;
}

همچنین اگر نکته‌ای، سوالی یا مطلبی بود که به نظرتون باید اضافه کنم بفرمایید.

باسپاس