ক্রমিউটেশনগুলি গণনা করুন যা প্রথমে কমছে তারপর C++ এ বাড়ছে

আমরা একটি পরিবর্তনশীল সংখ্যা. লক্ষ্য হল [1,সংখ্যা] এর মধ্যে সংখ্যার পারমুটেশনের গণনা খুঁজে বের করা যেখানে সংখ্যাগুলি প্রথমে কমছে তারপর বাড়ছে। যেমন num=3 হলে সংখ্যা 1,2,3। পারমুটেশন হবে [ 3,1,2 ] এবং [ 2,1,3] এবং গণনা হল 2৷

আমরা জানি যে প্রতিটি স্থানচ্যুতিতে সংখ্যার হ্রাস থেকে সংখ্যা বৃদ্ধির পরিবর্তনটি 1 এর অবস্থানের ভিত্তিতে সিদ্ধান্ত নেওয়া হবে যা সবচেয়ে ছোট। প্রতিটি 1 এর পরে সংখ্যা বাড়তে শুরু করবে। একটি ক্রমাগত হ্রাস এবং তারপর বৃদ্ধির জন্য, 1 অবস্থান 2 এবং সংখ্যা -1 এর মধ্যে থাকা উচিত। [ → ...1... → ]।

যদি 1 শুরুতে থাকে তবে সিরিজটি সম্পূর্ণভাবে বৃদ্ধি পাবে [ 1.. → ] , যদি এটি শেষে থাকে তবে সিরিজটি সম্পূর্ণভাবে হ্রাস পাবে [ … → 1 ]।

ধরা যাক আমাদের num=4 তারপর

আছে

1কে 2য় অবস্থানে রাখা, [ - , 1, - , - ]৷ 1ম অবস্থানের জন্য আমরা (2,3,4) থেকে বেছে নিতে পারি, ধরা যাক আমরা 2 বাছাই করি, তাহলে ক্রমটি হবে [ 2,1,3,4]। তাই এই ক্ষেত্রে 3C1 পারমুটেশন সম্ভব।

1কে 3য় অবস্থানে রাখা, [ -, -, 1, - ]। 1ম এবং 2য় অবস্থানের জন্য তিনটির মধ্যে যেকোনো দুটি নির্বাচন করুন (2,3,4)। মোট পারমুটেশন হবে ³ C₂ .

তাই মোট পারমুটেশন হবে =³ C₁ + ³ C₂ সংখ্যা=4

এর জন্য

যেকোনো x সংখ্যার জন্য, গণনা হবে =^x-1 C₁ + ^x-1 C₂ +......^x-1 C_c-2 =2_x-1 - 2 দ্বিপদ উপপাদ্য থেকে।

আসুন উদাহরণ দিয়ে বুঝতে পারি

ইনপুট − সংখ্যা=4

আউটপুট − ক্রমাগত সংখ্যা যা প্রথমে কমছে তারপর বাড়ছে:6

ব্যাখ্যা − পারমুটেশন হবে −

<প্রে>[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 দ্বিতীয় অবস্থানে[ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 তৃতীয় অবস্থানে

ইনপুট − সংখ্যা=6

আউটপুট − স্থান পরিবর্তনের সংখ্যা যা প্রথমে কমছে তারপর বৃদ্ধি পাচ্ছে −30

ব্যাখ্যা − কিছু পারমুটেশন হবে −

<প্রে>[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5]……[ 6, 5, 4, 3, 1, 2]।

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই পদ্ধতিতে আমরা একটি দ্বিপদী উপপাদ্য ব্যবহার করব যাতে উপরের সূত্র থেকে স্থানান্তরগুলি সরাসরি গণনা করা যায়। এছাড়াও আমরা একটি ফাংশন মান (লং লং i, লং লং num) তৈরি করব যা i^num প্রদান করে।

ইনপুট হিসাবে পরিবর্তনশীল সংখ্যা নিন।
ফাংশন permutations_increase_decrease(int num) num নেয় এবং ক্রমানুসারের সংখ্যা ফেরত দেয় যা প্রথমে কমছে তারপর সংখ্যা 1 থেকে সংখ্যা পর্যন্ত বৃদ্ধি পায়।
ফাংশন মান (লং লং i, লং লং নম) (ইনাম) % টেম্প গণনা করতে ব্যবহৃত হয়। যেখানে temp=1000000007.
ভিতর permutations_increase_decrease(int num) temp=1000000007 নিন।
যদি num 1 হয় তাহলে কোন পারমুটেশন সম্ভব নয় তাই 0 ফেরত দিন।
অন্য সেট গণনা =(মান (2, সংখ্যা - 1) - 2) % টেম্প ); সূত্র ব্যবহার করে।
ফলাফল হিসাবে রিটার্ন গণনা।

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;long long value(long long i, long long num){int temp =1000000007; যদি (সংখ্যা ==0){ ফেরত 1; } long long j =value(i, num / 2) % temp; j =(j * j) % temp; if(num &1){ j =(j * i) % temp; } রিটার্ন j;}int permutations_increase_decrease(int num){int temp =1000000007; যদি (সংখ্যা ==1){ ফেরত 0; } int গণনা =(মান (2, সংখ্যা - 1) - 2) % টেম্প; রিটার্ন কাউন্ট;}int main(){int num =4; cout<<"ক্রমানুবর্তনের সংখ্যা যা প্রথমে কমছে তারপর বাড়ছে:"< আউটপুট
 
 যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
 উৎপন্ন করবে ক্রমক্রমের সংখ্যা যা প্রথমে কমছে তারপর বাড়ছে:6