সমস্যা বিবৃতি
প্রতিটি প্রশ্নের জন্য N প্রশ্ন এবং K বিকল্প দেওয়া হয়েছে, যেখানে 1 <=N <=1000000000 এবং 1 <=K <=1000000000। কাজ হল 1 <=i <এর জন্য ith প্রশ্ন করার চেষ্টা করা খেলোয়াড়ের মোট সংখ্যার যোগফল নির্ধারণ করা। =k যেভাবেই হোক খেলা জিততে হবে। আপনাকে প্লেয়ারের মোট সংখ্যার যোগফল মিনিমাইজ করতে হবে এবং 109+7 মডিউল আউটপুট করতে হবে।
দয়া করে মনে রাখবেন যে কোনো ভুল উত্তর প্লেয়ারকে বাদ দিতে পারে
উদাহরণ
যদি N =5 এবং K =2 হয় তবে উত্তর হবে 62।
অ্যালগরিদম
- N th সমাধান করতে প্রশ্ন K খেলোয়াড়দের প্রয়োজন।
- সমাধান করতে (N-1) th প্রশ্ন K2 প্লেয়ার প্রয়োজন।
- একইভাবে এগিয়ে চলুন, 1 st সমাধান করতে প্রশ্ন KN খেলোয়াড়দের প্রয়োজন।
- সুতরাং, আমাদের সমস্যা GP টার্ম K + K 2 এর যোগফল খুঁজে পেতে কমিয়ে দেয়। + … + KN যা সমান:K(K n -1) / কে -1
উদাহরণ
#include <iostream>
#include <cmath>
#define MOD 1000000007
using namespace std;
long long int power(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1) {
res = res * a;
res = res % MOD;
}
b = b / 2;
a = a * a;
a = a % MOD;
}
return res;
}
long long getMinPlayer(long long n, long long k) {
long long num = ((power(k, n) - 1) + MOD) % MOD;
long long den = (power(k - 1, MOD - 2) + MOD) % MOD;
long long ans = (((num * den) % MOD) * k) % MOD;
return ans;
}
int main() {
long long n = 5, k = 2;
cout << "Minimum pairs = " << getMinPlayer(n, k) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMinimum pairs = 62
