b997. NOIP2016 Day2.1.组合数问题 - 高中生程式解題系統

內容

组合数 $C_{n}^{m}$ 表示的是从n个物品中选出m个物品的方案数。举个例子，从(1, 2, 3)三个物品中选择两个物品可以有(1, 2), (1, 3), (2, 3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：

$C_{n}^{m} = \frac{n!}{m! (n - m)!}$

其中 n! = 1 x 2 x ... x n。

小葱想知道如果给定n, m和k，对于所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足 $C_{i}^{j}$ 是k的倍数。

輸入說明

第一行有两个整数t, k，其中t代表该测试点总共有多少组测试数据，k的意义见【问题描述】。

接下来t行每行两个整数n, m，其中n, m的意义见【问题描述】。

輸出說明

t行，每行一个整数代表所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足 $C_{i}^{j}$ 是k的倍数。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1K
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1K

提示：

【样例1说明】

在所有可能的情况中，只有 $C_{2}^{1} = 2$ 是2的倍数。

【子任务】

测试点	n	m	k	t
1	≤3	≤3	=2	=1
2	=3	≤10000
3	≤7	≤7	=4	=1
4	=5	≤10000
5	≤10	≤10	=6	=1
6	=7	≤10000
7	≤20	≤100	=8	=1
8	=9	≤10000
9	≤25	≤2000	=10	=1
10	=11	≤10000
11	≤60	≤20	=12	=1
12	=13	≤10000
13	≤100	≤25	=14	=1
14	=15	≤10000
15	≤60	=16	=1
16	=17	≤10000
17	≤2000	≤100	=18	=1
18	=19	≤10000
19	≤2000	=20	=1
20	=21	≤10000

標籤:

出處:

NOIP 2016 提高组 Day2 第一题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」