組合數問題I(楊輝三角)

題目描述

組合數

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

其中n! = 1×2×…×n。

小蔥想知道如果給定n, m和k，對于所有的0≤i≤n,0≤ j≤min(i,m)有多少對(i, j)滿足

是k的倍數。

輸入

第一行有兩個整數t, k，其中t代表該測試點總共有多少組測試資料，k的意義見【問題描述】。接下來t行每行兩個整數n, m，其中n, m的意義見【問題描述】。

輸出

t行，每行一個整數代表所有的。0≤i≤n,0≤ j≤min(i,m)有多少對(i, j)滿足是k的倍數。

樣例輸入

1 2

3 3

樣例輸出

1

提示

在所有可能的情況中，隻有以

是2的倍數。3≤n,m≤2000,2≤k≤21,1≤t≤10000

思路

用楊輝三角模拟各個C(i,j)，最後根據得到的楊輝三角得出是k的倍數的組合數量

代碼實作

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
const int N=2010;
const int mod=1e9+7;
int yhs[N][N],num[N][N],line[N];
int n,m,t,k;
void build()
{
    for(int i=0; i<N; i++) yhs[i][0]=1;
    for(int i=1; i<N; i++)
    {
        for(int j=1; j<=i; j++)
        {
            yhs[i][j]=yhs[i-1][j-1]+yhs[i-1][j];
            yhs[i][j]%=k;
            if(yhs[i][j]==0) line[j]++;
            num[i][j]=num[i][j-1]+line[j];
        }
    }
}
int main()
{
    scanf("%d%d",&t,&k);
    build();
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(m>n)  m=n;
        printf("%d\n",num[n][m]);
    }
    return 0;
}