洛谷P2822 [NOIP2016 提高组] 组合数问题 题解

题目链接：P2822 [NOIP2016 提高组] 组合数问题

题意：

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

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $k|\binom{i}{j}$。

• 对于全部的测试点，保证 $0 \leq n, m \leq 2 \times 10^3$，$1 \leq t \leq 10^4$。

显然杨辉三角的那个预处理

询问可以用二维前缀和来搞

这里的前缀和有个有趣的地方

s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(c[i][j]==0)

这里在获取 $s_{i-1,j}$ 的时候，如果 $j=i$ ，那 $s_{i-1,j}$ 就没有算，会导致出错

解决的方法很简单，直接在每次计算时把 $s_{i,i+1}\leftarrow s_{i,i}$ 就好了

这样的话没有影响前缀和数组的意义，蛮好

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
#define _ 2000
int k,c[N][N],s[N][N];
void init()
{
    c[1][1]=1;
    for(int i=0; i<=_; i++) c[i][0]=1;
    for(int i=2; i<=_; i++)
        for(int j=1; j<=i; j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    for(int i=2; i<=_; i++)
    {
        for(int j=1; j<=i; j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(c[i][j]==0);
        s[i][i+1]=s[i][i];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,n,m;
    cin >> Q >> k;init();
    while(Q--)
    {
        cin >> n >> m;
        if(m>n)m=n;
        cout << s[n][m] << '\n';
    }
    return 0;
}