Masalalar
#035
~/algor $ cat masalalar/guruhlashlar-soni
Guruhlashlar soni
Qiyin
2000 ms
128 MB
60%
Mavzular:
Kombinatorika
Sinfda n ta o'quvchi bor. Ulardan k tasini olimpiadaga necha xil usulda tanlash mumkin? Tanlash tartibi ahamiyatsiz, ya'ni javob — C(n, k) guruhlashlar soni.
q ta so'rovga javob bering. Javoblar juda katta bo'lishi mumkin, shuning uchun 10⁹ + 7 ga bo'lgandagi qoldiqni chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda q. Keyingi q ta qatorning har birida ikkita son n va k.
Chiquvchi ma'lumotlar
Har bir so'rov uchun alohida qatorda C(n, k) mod (10⁹ + 7).
Izoh
1 ≤ q ≤ 10⁵
0 ≤ k ≤ n ≤ 10⁶
Misollar
Kirish #1
3 5 2 4 0 10 10
Chiqish #1
10 1 1
Kirish #2
1 1000000 500000
Chiqish #2
996692777