523 组合数问题

组合数 前缀和 T3 todo 523. 组合数问题 - AcWing题库

组合数 $C_n^m$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。 

举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2)$, $(1,3)$, $(2,3)$ 这三种选择方法。 

根据组合数的定义，我们可以给出计算组合数 $C_n^m$ 的一般公式：

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

其中 $n!=1\times 2\times \cdot \cdot \cdot \times n$。 

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

输入格式

第一行有两个整数 $t,k$ ，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n,m$，其中 $n,m$ 的意义见问题描述。

输出格式

共 $t$ 行，每行一个整数代表所有的 $0\le i\le n,0\le j\le min(i,m)$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。

数据范围

$1\le n,m\le 2000,2\le k\le 21,1\le t\le 10^4$

输入样例：

1 2
3 3

输出样例：

1

思路

简单看一下题意, 给你一个 $n,m$ 俩数, 求所有 $0\le i\le n,0\le j\le min\{i,m\}$ 的 $C_i^j$ 是 $k$ 的倍数的个数。

判断一个数是另一个数的倍数一般是通过取模运算 $a\mathrm{mod}b==0$ 时, 说明 $a$ 可以被 $b$ 整除, 也就是 $a$ 是 $b$ 的倍数。

这里则是统计$C_i^j\mathrm{mod}k==0$ 的个数, 可以先用 $O(n^2)$ 递推计算 $C_i^j\mathrm{mod}k$ 的值, 然后再前缀和统计所有取模后为0的值个数即可。

递推式原理是：$C_i^j=C_{i-1}^j+C_{i-1}^{j-1}$, 而前缀和则是矩阵前缀和。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 2e3 +10;
int f[N][N];
int res[N][N];
 
int n,m,k;
 
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(!j) f[i][j] = 1 % k;
            else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % k;
            
            if(!f[i][j]) res[i][j] = 1;
        }
    }
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            if(i) res[i][j] += res[i - 1][j];
            if(j) res[i][j] += res[i][j - 1];
            if(i && j) res[i][j] -= res[i - 1][j - 1];
        }
}
 
 
int main()
{
    int T;
    cin >> T >> k;
    init();
    while(T--)
    {
        int n,m;
        cin >> n >> m;
        cout << res[n][m] << endl;
    }
    
    return 0;
}