解题报告 P2822 组合数问题

题目内容

P2822

大意:给定 tkt 次给出 nm,询问所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 有多少对 (i,j) 满足 k|\binom{i}{j}

解题思路

因为数据范围中 n,m\leq 2000,所以不能直接把组合数存储起来,而注意到一个数据点中 k 是固定的,因此可以定义 f_{i,j} 为对于所有的 x\in[0,i]y\in[0,\min(j,x)] 中满足 k|\binom x y\binom x y 的个数。

可以使用递推法预处理所有的 \binom i j\bmod k,然后使用二维前缀和来处理 f_{i,j},每次 O(1) 回答询问。

c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];//下面解释
    }

上面是处理 f 的部分。每次求出组合数直接取模方便判断是否能被 k 整除。二维前缀和的递推都很容易看懂,但是对于最后的 f[i][i+1]=f[i][i]; 的理解是:由于每次 f[i][j] 都要加上 f[i-1][j],而不处理最后的 f[i][i+1] 的话会造成处理下一排时 f[i-1][j] 为 0,所以要进行这样的处理。

还有就是数据中可能有 n,这时候要进行特判

完整代码:

#include <cstdio>
#include <cctype>

//快读

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];
    }
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m>n?n:m]);
    }
    return 0;
}

当然还有另一种方法就不需要特判,如下:

#include <cstdio>
#include <cctype>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=2000;j++)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(i>=j && c[i][j]==0);
    //这里和上面一样,但是一定要注意判断这里的c[i][j]有没有意义,否则会抱灵
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注