CJOJ 2255 【NOIP2016】组合数问题 / Luogu 2822 组合数问题（递推）

Description

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

[C^m_n=frac{n!}{m!(n-m)!} ]

其中n! = 1 × 2 × · · · × n

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

Input

第一行有两个整数t,k，其中t代表该测试点总共有多少组测试数据。

接下来t行每行两个整数n,m。

Output

t行，每行一个整数代表答案。

Sample Input

1 2
3 3

Sample Output

Http

Luogu:https://www.luogu.org/problem/show?pid=2822
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2255

Source

递推

解决思路

不要被题目给出的那个式子给迷惑了！要是真按照那么算，肯定会爆掉！
这道题我们可以离线地来做。我们知道，计算组合数除了上面题目中给出的通项式之外，还有一个递推式：

[C^m_n=C^{m-1}_{n}+C^{m-1}_{n-1} ]

那么我们可以开一个二维数组存下所有的组合数（题目范围只有2000嘛）。至于是否整除的问题，我们可以在每一步计算的时候%k，这样既保证了不会爆掉long long 又能求出是否整除（若最后算出来是0就是可以整除啦）。

我们再把能整除的置为1，不能整除的置为0，求一下二维前缀和，然后就可以O(1)地回答询问啦。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int maxN=2000;
const int inf=2147483647;

int n,m,mod;
int C[maxN+10][maxN+10];
int If[maxN+10][maxN+10];

int main()
{
    int TT;
    cin>>TT>>mod;
    memset(C,0,sizeof(C));
    for (int i=0;i<=maxN;i++)//递推算出所有的组合数并取膜
    {
        C[i][0]=1;
        for (int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    for (int i=0;i<=maxN;i++)
        for (int j=0;j<=i;j++)//构造二维前缀和初值
            If[i][j]=(bool)(C[i][j])^1;
    /*for (int i=0;i<=10;i++)
    {
        for (int j=0;j<=10;j++)
            cout<<If[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;*/
    for (int i=1;i<=maxN;i++)//计算二维前缀和
        for (int j=1;j<=maxN;j++)
            If[i][j]=If[i][j]+If[i-1][j]+If[i][j-1]-If[i-1][j-1];
    /*for (int i=0;i<=10;i++)
    {
        for (int j=0;j<=10;j++)
            cout<<If[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;*/
    for (int ti=1;ti<=TT;ti++)//回答询问
    {
        cin>>n>>m;
        cout<<If[n][m]<<endl;
    }
    return 0;
}