Đề bài
Cho N câu hỏi và K lựa chọn cho mỗi câu hỏi, với 1 ≤ N ≤ 1.000.000.000 và 1 ≤ K ≤ 1.000.000.000. Nhiệm vụ là xác định tổng số người chơi đã thử câu hỏi i cho tất cả 1 ≤ i ≤ k để thắng trò chơi bằng cách nào đó. Bạn phải tối thiểu hóa tổng số người chơi và xuất kết quả modulo 10^9+7.
Lưu ý rằng bất kỳ câu trả lời sai nào cũng dẫn đến việc loại người chơi đó.
Ví dụ
Nếu N = 5 và K = 2 thì câu trả lời là 62.
Thuật toán
- Để giải câu hỏi thứ N cần K người chơi.
- Để giải câu hỏi thứ (N-1) cần K^2 người chơi.
- Tương tự tiến về phía trước, để giải câu hỏi thứ 1 cần K^N người chơi.
- Vì vậy, bài toán归结为 tìm tổng các số hạng của dãy GP: K + K^2 + ... + K^N bằng K(K^N - 1) / (K - 1).
Ví dụ
#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 << "Số cặp tối thiểu = " << getMinPlayer(n, k) << endl;
return 0;
}
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Số cặp tối thiểu = 62