2028 . 反應遲鈍
TopCoder
Tags
Description
對質數$P$和整數$1\leq X \leq P - 1$ ，定義$f(P,X,K)$為從$(1,2,\dots,P-1)$中刪除$X$後得到的$P-2$元集合中所有$K$元子集合的積的和。
例如$f(7,5,3)=260$。
因為$(1,2,3,4,6)$中的$3$元子集合有$(1,2,3),(1,2,4),(1,2,6),(1,3,4),(1,3,6),(1,4,6),(2,3,4),(2,3,6),(2,4,6),(3,4,6)$，
故$f(7,5,3)=6+8+12+12+18+24+24+36+48+72=260$
給定$P,X,K$請求出$f(P,X,K)$%$P$
Input Format
第一行有兩個正整數$Q, P$，代表測資筆數和給定的質數。
接下來每一筆測資中，有兩個非負整數$X,K\geq 1$
Output Format
對於每筆測資，輸出$f(P,X,K)$%$P$。
Sample Input 1
1 7
5 3
5 3
Sample Output 1
1
Sample Input 2
2 11
10 5
6 7
10 5
6 7
Sample Output 2
1
3
3
Sample Input 3
1 1000000007
30 60
30 60
Sample Output 3
384495340
Hints
本題共有兩組測試資料。每組可有多個輸入檔案，全部答對該組才得分。
第一組30分，$Q=1, P\leq 20$
第二組70分，$Q\leq 10^ 5,P\leq 2\times 10^ 9 $
Problem Source
rsabcmoi
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~5 | 30 |
| 2 | 0~9 | 70 |