題目描述：
題目連結： UOJ 263 http://uoj.ac/problem/263
題目背景: NOIP2016 提高組 Day2 T1
組合數 表示的是從 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：
1 2
3 3
樣例輸出1：
1
樣例輸入2：
2 5
4 5
6 7
樣例輸出2：
7
備注：
樣例1說明：在所有可能的情況中，隻有 是 2 的倍數。
資料規模與約定：
題目分析：
由組合數與楊輝三角的對應關系可知遞推公式。令 f[i][j] 代表
，得 f[i][j]=f[i−1][j−1]+f[i−1][j] 。是以我們可以預處理出所有組合數，就得知是否是k的倍數。為避免爆int，更新時模k,這不影響判斷。再開一個數組 ans[i][j] ,記錄對于i這一維到j時滿足要求的數的個數。最後答案就是累加 ans[1][min(1,j)]+ans[2][min(2,j)]+⋅⋅⋅⋅⋅⋅+ans[i][min(i,j)] 。
附代碼：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=;
const int N=+;
int t,k,maxx,maxy,f[maxn][maxn],ans[maxn][maxn],n[N],m[N],sum;
void pre()
{
f[][]=;
for(int i=;i<=maxx;i++)
for(int j=;j<=i;j++)
{
f[i][j]=(f[i-][j-]+f[i-][j])%k;
if(f[i][j]==) ans[i][j]++;
ans[i][j]+=ans[i][j-];
}
}
int main()
{
//freopen("lx.in","r",stdin);
scanf("%d%d",&t,&k);
for(int i=;i<=t;i++)
{
scanf("%d%d",&n[i],&m[i]);
if(n[i]>maxx) maxx=n[i];
if(m[i]>maxy) maxy=m[i];
}
pre();
for(int i=;i<=t;i++)
{
sum=;
for(int j=;j<=n[i];j++)
{
int v=min(j,m[i]);
sum+=ans[j][v];
}
printf("%d\n",sum);
}
return ;
}