Learn Contest Programming

প্রথমেই আসি মডুলার ইনভার্স কি? দুটি সংখ্যার যোগ, বিয়োগ, গুনের ক্ষেত্রে আমরা নিচের রুলস গুলো অ্যাপ্লাই করতে পারি। 1. (a+b) mod m = ((a mod m) + (b mod m)) mod m   2. (a-b) mod m = ((a mod m) - (b mod m)) mod m   3. (a*b) mod m =((a mod m) * (b mod m)) mod m কিন্ত ভাগের ক্ষেত্রে এই রুলস এপ্লিকেবল না।     তার মানে তুমি (a/b) mod m = ((a mod m) / (b mod m)) mod m লিখতে পারবা না। উদাহরনঃ (12/3) mod 3 = 4 mod 3 = 1   But, ((12 mod 3)/(3 mod 3)) mod 3 = (0/0) mod 3 = undefined!!   Clearly they aren't same.   b এবং m যদি পরস্পর সহমৌলিক হয়, অর্থাৎ GCD(b,m)=1 হয় তবে তুমি মডুলার ইনভার্স ব্যাবহার করে (a/b) mod m বের করতে পারবে। খেয়াল কর, (a/b) mod m = (a*(b^-1)) mod m = ((a mod m)* ((b^-1) mod m)) mod m   এখন তোমার দরকার (b^-1) mod m এর মান। এই মানটা পেয়ে গেলে জাস্ট Big Mod ইউজ করে (a mod m) এর সাথে গুন করে দিলেই হলো। কিভাবে (b^-1) mod m এর মান বের করবে? ফার্মার লিটল থিওরেম অনুসারে b এবং m যদি পরস্পর সহমৌলিক হয় তাহলে, b^m mod m = b mod m  

আসসালামুআলাইকুম। আমি আজকে ভেক্টর নিয়ে কিছু লিখছি। এটা আশা করি অনেকেই ব্যবহার করতে পার। যারা যারা পারনা তাদের জন্যই মূলত এই লেখা। ভেক্টর C++ এর STL (Standard Template Library) এর একটা কন্টেইনার। STL কন্টেইনারের মধ্যে আরো আছে ম্যাপ, সেট, কিউ, ডি-কিউ, স্ট্যাক ইত্যাদি। সেগুলো নিয়ে পরে আলোচনা করবো। C/C++ এ অ্যারে আমরা সবাই ব্যবহার করেছি। ভেক্টর হচ্ছে অ্যারেরই স্পেশালাইজড রুপ যা প্রায় অ্যারের মতই, কিন্তু এতে অনেক সুবিধা আছে যা অ্যারেতে নাই। প্রথমত, এটার সাইজ অ্যারের মত ফিক্সড রাখা লাগেনা। চাইলে ইচ্ছামত এক্সটেন্ড করা যায়। তাই যদি তোমার মনে হয় যে এমন একটা অ্যারে নিবা যেটার সাইজ আগে থেকে ডিফাইন না করে আস্তে আস্তে এটায় একটা একটা করে সংখ্যা রাখবা তখন ভেক্টর ব্যাবহার করতে পার। আবার চাইলে আগে থেকে অ্যারের মত ভেক্টরের সাইজ ও ডিফাইন করে আসতে পারো। প্রবলেম নাই। ভেক্টরের ম্যানিপুলেশন অ্যারের তুলনায় অনেক সহজ, যা তোমাকে প্রবলেম সল্ভিং এর সময় দ্রুত ও নির্ভুল ভাবে ইমপ্লিমেন্টেশন করতে সাহায্য করবে। এখানে ভেক্টরের কিছু বহুল ব্যবহৃত ফাংশনের কাজ দেখাচ্ছি। নোটঃ আমি long long এর স্থলে