কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।
অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)
(x + y)0 = 1
(x + y)1 = x + y
আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) n
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1 4 6 4 1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ
(x + y)n = (nC0)(xny0) + (nC1)(xn-11y1) + (nC2)(xn-22y2) + ... + (nCn)(x0yn); [nCk = combnation of k element from n or n choose k]
আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ
কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।
অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)
বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )
বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন।
আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ
(x + y)0 = 1
(x + y)1 = x + y
(x + y)2 = x2 + 2xy + y2
(x + y)3 = x3 + 3x2y + 3xy2 + y3
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ
আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) n
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ
আমরা n = 4 নিয়ে দেখিঃ
(1 + x)4 = x4 + 4x3 + 6x2 + 4x + 1এখন কো-এফিশিয়েন্টগুলি হবেঃ 1 4 6 4 1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ
(x + y)n = (nC0)(xny0) + (nC1)(xn-11y1) + (nC2)(xn-22y2) + ... + (nCn)(x0yn); [nCk = combnation of k element from n or n choose k]
আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ
১। ফ্যাক্টরিয়াল ( Factorial )
আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk = [ n! ] / [ k! * (n-k)! ]
ফর্মুলাঃ nCk = [ n! ] / [ k! * (n-k)! ]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| ll nCr(ll n, ll r) | |
| { | |
| ll f[n + 1]; | |
| f[0] = 1; | |
| for (ll i = 1; i <= n; i++) | |
| f[i] = i * f[i-1]; | |
| return f[n] / f[r] / f[n-r]; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r) | |
| { | |
| cout << nCr(n, Min(r,n-r)) << endl; | |
| } | |
| return 0; | |
| } |
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।
২। রিকার্সন ( Recursion )
nCk বের করার রিকার্সন ফর্মুলা হলঃ nCk (i,k) = nCk (i-1,k-1) + nCk (i-1,k);
আমাদের টাইম এবং স্পেস কমপ্লেক্সিটি হবেঃ O(n*k) for nCk
আমরা একে একটু মডিফাই করে স্পেস কমপ্লেক্সিটি কমিয়ে আনতে পারি। আমরা আগের সারি চেক করবো, কারন আমাদের ঐ সারিগুলো আসলে দরকার হবেনা পরে আর।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| ll nCr(ll n, ll r, ll MOD) | |
| { | |
| vector< vector<ll> > nCr(n+1,vector<ll> (r+1,0)); | |
| for(ll i = 0; i <= n; i++) | |
| { | |
| for(ll k = 0; k <= r && k <= i; k++) | |
| if(k == 0 || k == i) | |
| nCr[i][k] = 1; | |
| else | |
| nCr[i][k] = (nCr[i-1][k-1] + nCr[i-1][k])%MOD; | |
| } | |
| return nCr[n][r]; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r >> m) | |
| { | |
| cout << nCr(n, r, m) << endl; | |
| } | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| ll nCr(ll n, ll r, ll MOD) | |
| { | |
| vector< vector<ll> > nCr(2,vector<ll> (r+1,0)); | |
| for(ll i = 0; i <= n; i++) | |
| { | |
| for(ll k = 0; k <= r && k <= i; k++) | |
| if(k == 0 || k == i) | |
| nCr[i&1][k] = 1; | |
| else | |
| nCr[i&1][k] = (nCr[(i-1)&1][k-1] + nCr[(i-1)&1][k])%MOD; | |
| } | |
| return nCr[n&1][r]; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r >> m) | |
| { | |
| cout << nCr(n, r, m) << endl; | |
| } | |
| return 0; | |
| } |
৩। কম্বিনেশন এর বিস্তার ( Expansion of Combination )
আমরা জানি, nCk = [ n! ] / [ k! * (n-k)! ], অর্থাৎ
[ n(n-1)(n-2) ... (n-k+1) ] [ (n-k) ... (1) ]
-------------------------------------------------------------------------
[ (n-k) ... (1) ] [ k(k-1)(k-2) .... (1) ]
আমরা লব এবং হর থেকে [ (n-k) ... (1) ] টার্ম কেটে ফেলতে পারি, তাহলে আমাদের ফাইনাল টার্ম হবেঃ
n (n-1) (n-2) (n-k+1)
n (n-1) (n-2) (n-k+1)
--- * ------ * ------ * ----------
k (k-1) (k-2) (1)
আমরা একে এভাবে লিখতে পারিঃ
nCk (n,k) = 1 ; if k == 0
আমরা একে এভাবে লিখতে পারিঃ
nCk (n,k) = 1 ; if k == 0
else (n/k) * nCk (n-1, k-1)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| ll nCr(ll n, ll r) | |
| { | |
| if (r==0) return 1; | |
| else return nCr(n-1,r-1) * n / r; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r) | |
| { | |
| cout << nCr(n, Min(r, n-r)) << endl; | |
| } | |
| return 0; | |
| } |
৪। প্রাইম এর পাওয়ার ( Power of Prime )
আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ
Pprime = floor[ n/prime ] + floor[ n/prime2 ] + .....
এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা ppower করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।
Pprime = floor[ n/prime ] + floor[ n/prime2 ] + .....
এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা ppower করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| /* This function calculates power of p in n! */ | |
| ll fact(ll n, ll p) | |
| { | |
| ll k = 0; | |
| while (n > 0) | |
| { | |
| k += n/p; | |
| n /= p; | |
| } | |
| return k; | |
| } | |
| /* This function calculates (a^b)%MOD */ | |
| ll modPow(ll a, ll b, ll MOD) | |
| { | |
| ll x = 1, y = a; | |
| while(b > 0) | |
| { | |
| if(b%2 == 1) | |
| { | |
| x = (x*y); | |
| if(x > MOD) x %= MOD; | |
| } | |
| y = (y * y); | |
| if(y > MOD) y %= MOD; | |
| b /= 2; | |
| } | |
| return x; | |
| } | |
| ll nCr(ll n, ll r, ll MOD) | |
| { | |
| ll res = 1; | |
| vector<bool> isPrime(n+1,1); | |
| for(ll i = 2; i <= n; i++) | |
| if(isPrime[i]) | |
| { | |
| for(ll j = 2*i; j <= n; j += i) | |
| isPrime[j]=0; | |
| ll power = fact(n,i) - fact(r,i) - fact(n-r,i); | |
| res = (res * modPow(i, power, MOD)) % MOD; | |
| } | |
| return res; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r >> m) | |
| { | |
| cout << nCr(n, r, m) << endl; | |
| } | |
| return 0; | |
| } |
৫। চাইনিজ রিমেইন্ডার থিওরেম ( Chinese Remainder Theorem )
যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| #define Min(a,b) (a<=b)? a : b | |
| /* This function calculates (a^b)%MOD */ | |
| ll modPow(ll a, ll b, ll MOD) | |
| { | |
| ll x = 1, y = a; | |
| while(b > 0) | |
| { | |
| if(b%2 == 1) | |
| { | |
| x = (x*y); | |
| if(x > MOD) x %= MOD; | |
| } | |
| y = (y * y); | |
| if(y > MOD) y %= MOD; | |
| b /= 2; | |
| } | |
| return x; | |
| } | |
| /* Modular Multiplicative Inverse | |
| Using Euler's Theorem | |
| a^(phi(m)) = 1 (mod m) | |
| a^(-1) = a^(m-2) (mod m) */ | |
| ll invMod(ll n, ll MOD) | |
| { | |
| return modPow(n,MOD-2,MOD); | |
| } | |
| ll nCr(ll n, ll r, ll MOD) | |
| { | |
| vector<ll> f(n + 1,1); | |
| for(ll i = 2; i <= n; i++) | |
| f[i] = (f[i-1] * i) % MOD; | |
| return (f[n]*((invMod(f[r], MOD) * invMod(f[n-r], MOD)) % MOD)) % MOD; | |
| } | |
| int main() | |
| { | |
| ll n,r,m; | |
| while (cin >> n >> r >> m) | |
| { | |
| cout << nCr(n, r, m) << endl; | |
| } | |
| return 0; | |
| } |
No comments:
Post a Comment