洛谷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;
}