NOIP2016Day2T1-組合數問題

A: 組合數問題

時間限制: 1 Sec   記憶體限制: 512 MB

題目描述

組合數C(n,m)表示的是從 n 個物品中選出 m 個物品的方案數。舉個例子，從 (1, 2, 3) 三個物品中選擇兩個物品可以有 (1, 2),(1, 3),(2, 3) 這三種選擇方法。根據組合數的定義，我們可以給出計算組合數C(n,m)的一般公式： C(n,m)=n!/(m!(n-m)!)

其中 n ! =  1 × 2 ×···× 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 2 3 3

2 5 4 5 6 7

樣例輸出

1

0 7

提示

【樣例 1 說明】

在所有可能的情況中，隻有C(2,1)=2 是2的倍數。

【子任務】

測試點	n	m	k	t
1	≤ 3	≤ 3	= 2	= 1
2	= 3	≤ 104
3	≤ 7	≤ 7	= 4	= 1
4	= 5	≤ 104
5	≤ 10	≤ 10	= 6	= 1
6	= 7	≤ 104
7	≤ 20	≤ 100	= 8	= 1
8	= 9	≤ 104
9	≤ 25	≤ 2000	= 10	= 1
10	= 11	≤ 104
11	≤ 60	≤ 20	= 12	= 1
12	= 13	≤ 104
13	≤ 100	≤ 25	= 14	= 1
14	= 15	≤ 104
15	≤ 60	= 16	= 1
16	= 17	≤ 104
17	≤ 2000	≤ 100	= 18	= 1
18	= 19	≤ 104
19	≤ 2000	= 20	= 1
20	= 21	≤ 104

我們可以先求出C(i,j)的值。通過找規律可以發現這是一個楊輝三角。可以求出記為f[i,j]并 mod k。然後記dp[i,j]為C(i,j)的個數。當f[i,j]=0時，dp[i,j]=dp[i,j-1]+1，否則dp[i,j]=dp[i,j-1]。最後每組從1到m循環一遍求解即可。

Code：

var
  t,k,i,j,ans,n,m:longint;
  dp,f:array[0..2000,0..2000] of longint;
begin
  readln(t,k);
  for i:=0 to 2000 do f[i,0]:=1;
  for i:=1 to 2000 do
    for j:=1 to i do
      f[i,j]:=(f[i-1,j]+f[i-1,j-1]) mod k;
  for i:=1 to 2000 do
    for j:=1 to i do
      if f[i,j]=0 then
        dp[i,j]:=dp[i,j-1]+1 else
          dp[i,j]:=dp[i,j-1];
  for i:=1 to t do
  begin
    ans:=0;
    readln(n,m);
    for j:=1 to n do
      if j>m then ans:=ans+dp[j,m]
        else ans:=ans+dp[j,j];
    writeln(ans);
  end;
end.