b514:
魔法分配 (MagicDistribution)
Content
魔法學院中，有n 位學生，學院要舉辦一場魔法對抗賽。教練想要從這n 位學生中選出m 位學生組成一
支代表隊，可是這樣有太多不同的方法了！現在有q 個詢問，每個詢問給定n 和m，請你計算出從n 位
學生中選出m 位學生組成一支代表隊，有多少種不同的選法？由於答案可能很大，請輸出結果對給定的
質數p 取模的值。
Input
輸入格式
q p
n_1 m_1
n_2 m_2 ...
n_q m_q
其中：
• q 表示詢問的數量
• p 是一個質數，用於取模運算
• 接下來q 行，每行包含兩個整數n_i 和m_i
Output
輸出格式
ans_1
ans_2 ...
ans_q
對於每個詢問，輸出一行表示選法的總數模p 的值。
Sample Input
#1
3 11 5 2 7 3 17 4
Sample Output
#1
10 2 4
測資資訊：
記憶體限制：
256
MB
不公開 測資點#0 (2%): 0.2s , <1K
不公開 測資點#1 (2%): 0.2s , <1K
不公開 測資點#2 (2%): 0.2s , <1K
不公開 測資點#3 (2%): 0.2s , <1K
不公開 測資點#4 (2%): 0.2s , <1K
不公開 測資點#5 (2%): 0.2s , <1K
不公開 測資點#6 (2%): 0.2s , <1K
不公開 測資點#7 (2%): 0.2s , <1K
不公開 測資點#8 (2%): 0.2s , <1K
不公開 測資點#9 (2%): 0.2s , <1K
不公開 測資點#10 (2%): 0.2s , <1K
不公開 測資點#11 (2%): 0.2s , <1K
不公開 測資點#12 (2%): 0.2s , <1K
不公開 測資點#13 (2%): 0.2s , <1K
不公開 測資點#14 (2%): 0.2s , <1K
不公開 測資點#15 (2%): 0.2s , <1K
不公開 測資點#16 (2%): 0.2s , <1K
不公開 測資點#17 (2%): 0.2s , <1K
不公開 測資點#18 (2%): 0.2s , <1K
不公開 測資點#19 (2%): 0.2s , <1K
不公開 測資點#20 (2%): 0.2s , <1M
不公開 測資點#21 (2%): 0.2s , <1M
不公開 測資點#22 (2%): 0.2s , <1M
不公開 測資點#23 (2%): 0.2s , <1M
不公開 測資點#24 (2%): 0.2s , <1M
不公開 測資點#25 (2%): 0.2s , <1M
不公開 測資點#26 (2%): 0.2s , <1M
不公開 測資點#27 (2%): 0.2s , <1M
不公開 測資點#28 (2%): 0.2s , <1M
不公開 測資點#29 (2%): 0.2s , <1M
不公開 測資點#30 (2%): 1.0s , <1M
不公開 測資點#31 (2%): 1.0s , <1M
不公開 測資點#32 (2%): 1.0s , <10M
不公開 測資點#33 (2%): 1.0s , <10M
不公開 測資點#34 (2%): 1.0s , <10M
不公開 測資點#35 (2%): 1.0s , <10M
不公開 測資點#36 (2%): 1.0s , <10M
不公開 測資點#37 (2%): 1.0s , <10M
不公開 測資點#38 (2%): 1.0s , <10M
不公開 測資點#39 (2%): 1.0s , <10M
不公開 測資點#40 (2%): 1.0s , <1M
不公開 測資點#41 (2%): 1.0s , <10M
不公開 測資點#42 (2%): 1.0s , <10M
不公開 測資點#43 (2%): 1.0s , <10M
不公開 測資點#44 (2%): 1.0s , <1M
不公開 測資點#45 (2%): 1.0s , <10M
不公開 測資點#46 (2%): 1.0s , <10M
不公開 測資點#47 (2%): 1.0s , <10M
不公開 測資點#48 (2%): 1.0s , <10M
不公開 測資點#49 (2%): 1.0s , <10M
不公開 測資點#0 (2%): 0.2s , <1K
不公開 測資點#1 (2%): 0.2s , <1K
不公開 測資點#2 (2%): 0.2s , <1K
不公開 測資點#3 (2%): 0.2s , <1K
不公開 測資點#4 (2%): 0.2s , <1K
不公開 測資點#5 (2%): 0.2s , <1K
不公開 測資點#6 (2%): 0.2s , <1K
不公開 測資點#7 (2%): 0.2s , <1K
不公開 測資點#8 (2%): 0.2s , <1K
不公開 測資點#9 (2%): 0.2s , <1K
不公開 測資點#10 (2%): 0.2s , <1K
不公開 測資點#11 (2%): 0.2s , <1K
不公開 測資點#12 (2%): 0.2s , <1K
不公開 測資點#13 (2%): 0.2s , <1K
不公開 測資點#14 (2%): 0.2s , <1K
不公開 測資點#15 (2%): 0.2s , <1K
不公開 測資點#16 (2%): 0.2s , <1K
不公開 測資點#17 (2%): 0.2s , <1K
不公開 測資點#18 (2%): 0.2s , <1K
不公開 測資點#19 (2%): 0.2s , <1K
不公開 測資點#20 (2%): 0.2s , <1M
不公開 測資點#21 (2%): 0.2s , <1M
不公開 測資點#22 (2%): 0.2s , <1M
不公開 測資點#23 (2%): 0.2s , <1M
不公開 測資點#24 (2%): 0.2s , <1M
不公開 測資點#25 (2%): 0.2s , <1M
不公開 測資點#26 (2%): 0.2s , <1M
不公開 測資點#27 (2%): 0.2s , <1M
不公開 測資點#28 (2%): 0.2s , <1M
不公開 測資點#29 (2%): 0.2s , <1M
不公開 測資點#30 (2%): 1.0s , <1M
不公開 測資點#31 (2%): 1.0s , <1M
不公開 測資點#32 (2%): 1.0s , <10M
不公開 測資點#33 (2%): 1.0s , <10M
不公開 測資點#34 (2%): 1.0s , <10M
不公開 測資點#35 (2%): 1.0s , <10M
不公開 測資點#36 (2%): 1.0s , <10M
不公開 測資點#37 (2%): 1.0s , <10M
不公開 測資點#38 (2%): 1.0s , <10M
不公開 測資點#39 (2%): 1.0s , <10M
不公開 測資點#40 (2%): 1.0s , <1M
不公開 測資點#41 (2%): 1.0s , <10M
不公開 測資點#42 (2%): 1.0s , <10M
不公開 測資點#43 (2%): 1.0s , <10M
不公開 測資點#44 (2%): 1.0s , <1M
不公開 測資點#45 (2%): 1.0s , <10M
不公開 測資點#46 (2%): 1.0s , <10M
不公開 測資點#47 (2%): 1.0s , <10M
不公開 測資點#48 (2%): 1.0s , <10M
不公開 測資點#49 (2%): 1.0s , <10M
Hint ：
測支解釋
• 第一組n=5,m=2 有10 種選法：
{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}
• 第二組n=7,m=3 有35 種選法，模11 餘2
• 第三組n=17,m=4 有2380 種選法，模11 餘4
約束條件
• 1 ≤ q ≤ 10_5
• 1 ≤ p ≤ 10_7，且p 是質數
• 0 ≤ m_i ≤ n_i ≤ 10^100
子任務
1.（20 分）p ≤ 100，n_i ≤ p，q ≤ 10
2.（20 分）p ≤ 100，n_i ≤ p^2，q ≤ 100
3.（20 分）p ≤ 1000，n_i ≤ p^3，q ≤ 1000
4.（20 分）p ≤ 10^6，n_i ≤ 10^18，q ≤ 10^5
5.（20 分）保證q ≤ 10^6/logp(n)，且p,q,n,m 符合約束條件。
出處:
PCOI 2025 第一季
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||