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;

}

巴特西

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

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

Description

Input

Output

Sample Input

Sample Output

Http

Source

解决思路

代码

最新文章

热门文章

巴特西

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

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

Description

Input

Output

Sample Input

Sample Output

Http

Source

解决思路

代码

最新文章

热门文章

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

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