คำชี้แจงปัญหา
ให้คำถาม N คำถามและตัวเลือก K สำหรับแต่ละคำถาม โดยที่ 1 <=N <=1000000000 และ 1 <=K <=1000000000 ภารกิจคือการกำหนดผลรวมของจำนวนผู้เล่นทั้งหมดที่พยายามถามคำถามสำหรับทั้ง 1 <=i <=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) / 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
