সমস্যা বিবরণ
Nটি প্রশ্ন এবং প্রতিটি প্রশ্নের জন্য Kটি অপশন দেওয়া আছে, যেখানে 1 ≤ N ≤ 1000000000 এবং 1 ≤ K ≤ 1000000000। টাস্ক হলো ১ ≤ i ≤ K এর জন্য i-তম প্রশ্নে অ্যাটেম্প্ট করা মোট প্লেয়ার সংখ্যার সমষ্টি বের করা যাতে গেম যেভাবেই জয় করা যায়। আপনাকে মোট প্লেয়ার সংখ্যার সমষ্টি মিনিমাইজ করতে হবে এবং আউটপুট দিতে হবে মডুলো 10⁹+৭ দিয়ে।
দ্রষ্টব্য: যেকোনো ভুল উত্তর প্লেয়ারকে এলিমিনেট করবে।
উদাহরণ
যদি N = 5 এবং K = 2 হয়, তবে উত্তর ৬২।
অ্যালগরিদম
- N-তম প্রশ্ন সমাধানের জন্য K প্লেয়ার দরকার।
- (N-1)-তম প্রশ্ন সমাধানের জন্য K² প্লেয়ার দরকার।
- এভাবে চলতে থাকলে, ১-স্ট প্রশ্ন সমাধানের জন্য Kᴺ প্লেয়ার দরকার।
- সেজন্য, আমাদের সমস্যা রিডিউস হয় GP টার্মগুলোর সমষ্টি বের করতে: K + K² + … + Kᴺ যা সমান: K(Kⁿ - 1) / (K - 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
