ข้อความโจทย์
กำหนด N คำถามและ K ตัวเลือกสำหรับแต่ละคำถาม โดยที่ 1 <= N <= 1,000,000,000 และ 1 <= K <= 1,000,000,000 งานคือหาผลรวมของจำนวนผู้เล่นทั้งหมดที่พยายามตอบคำถามที่ i สำหรับทั้ง 1 <= i <= k เพื่อชนะเกมอย่างใดอย่างหนึ่ง คุณต้องลดผลรวมของจำนวนผู้เล่นทั้งหมดและแสดงผลโมดูล로 10^9+7
โปรดทราบว่าคำตอบผิดจะนำไปสู่การตัดสินผู้เล่นออก
ตัวอย่าง
ถ้า N = 5 และ K = 2 คำตอบคือ 62
อัลกอริทึม
- เพื่อแก้คำถามที่ N ต้องการผู้เล่น K คน
- เพื่อแก้คำถามที่ (N-1) ต้องการผู้เล่น K^2 คน
- เช่นเดียวกันไปเรื่อยๆ เพื่อแก้คำถามที่ 1 ต้องการผู้เล่น K^N คน
- ดังนั้นโจทย์ลดรูปเป็นการหาผลรวมของพจน์ GP คือ K + K^2 + ... + K^N ซึ่งเท่ากับ: 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
