题目描述

    组合数表示的是从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

 

题目思路：提及组合数，他的公式 我们 也都背过了。而对于这个题而言，n的范围1-2000,2000的阶乘怎么办？显然这个题目的提示就是在坑我们，使得我们转换不了思路。不要被它迷惑，想一下组合数其实还有一个 递推公式  ：c(m,n)=c(m-1,n-1)+c(m-1,n)

于是我们可以根据这个事先把所有的都放到一个数组中，其实 如果你对 杨辉 熟悉的话，你就会知道这其实就是 杨辉三角

所以我们事先打表，打表一个杨辉三角，然后枚举 每一个 C(i  ,  j)看其是否为 k 的倍数。

但是下面需要进行一些细节操作：

1.由于数字太大，而且杨辉三角打表，打到第五十行杨辉三角的值就会爆long long，何况2000！所以我们怎么让他不爆呢？我们可以跟具题意想一下，既然 要判断是不是 k的倍数，我们可以把每一个 杨辉三角的值都对k取余，那么他们的值就变成了 [0,k），所以说我们再判断的时候，我们只需要判断 c(i,j) 是否为0即可，并且这样打表 不可能爆 long long，因为k<21，int也足够了。

2. 这个题目还要卡一个时间，意思就是你这样交上去是过不了的，我测试了一下(根据洛谷)，有两个会T掉，所以说我们需要再优化！！具体的时间浪费在哪里？因为我们要遍历 c(i,min(j,m))，i<2000,m<2000.这样就是 4000000，再加外层循环 t 100000 ，怕是1s很难过这道题了，因为t的数值 没法改变，我们只能改变 遍历的时间，所以说这里 引入一个 辅助工具，叫做前缀和数组：

因为我们的打表是在 t循环外面的，所以我们可以，将每一行 到 第i列的时候，0的个数有多少个记录下来，之后只需要遍历每一行就可以了 即ans+=num[i][min(m,j)]，所以这样复杂度就优化到了 2000，这样就不会超时了。

还有很多细节和思路我都写在注释里了：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#include <stdlib.h>
#include <time.h>
#include <sstream>
#define mem(a,b) memset(a,b,sizeof(a))
#include <string>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*坚持不懈，无懈可击*/
int ta[3000][3000];
int num[3000][3000];
void set_table(int mod)
{
    memset(num,0,sizeof(num));
    for(int i=1;i<2000;i++)
        ta[i][0]=1;
    ta[1][1]=1;
    for(int i=2;i<2000;i++)
        for(int k=1;k<=i;k++)
        {
            ta[i][k]=(ta[i-1][k-1]+ta[i-1][k])%mod;//同余模定理    
            if(ta[i][k]==0)//更新前缀和数组
                num[i][k]=num[i][k-1]+1;//如果当前是1，那么肯定比之前多了一个1
            else
                num[i][k]=num[i][k-1];//否则不变
        }
}
int main()
{
    int n,m,k;
    int t;
    scanf("%d%d",&t,&k);
        set_table(k);//一定要注意在循环外面打表
    while(t--)
    {
        ll ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            int z=min(i,m);//遍历每一行，到第几列的前缀和即可
                ans+=num[i][z];
        }
        printf("%lld\n",ans);//最后输出
    }
    return 0;
}

我们由此可见，在某些题目中尤其是 控制循环 一次打表的题目中，我们可以利用 前缀和数组 大大的优化时间。