组合数问题

组合数问题

2024 年 01 月 22 日

722 次浏览

1196字数

题目描述

组合数 $\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}$。

输入格式

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

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

输出格式

共 t 行，每行一个整数代表所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 中有多少对 (i,j) 满足 $k|\binom{i}{j}$。

输入输出样例

输入 #1

1 2
3 3

输出 #1

输入 #2

2 5
4 5
6 7

输出 #2

0
7

说明/提示

【样例1说明】

在所有可能的情况中，只有 $\binom{2}{1} = 2$ 一种情况是 2 的倍数。

【子任务】

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

题目分析

利用组合的一个性质：

$$ C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1} $$

可以预处理$C_i^j,0\leq j \leq i\leq n$ 。复杂度$O(n^2)$

c[0][0]=c[1][0]=c[1][1]=1;
for(int i=2;i<=N-5;i++){
    for(int j=0;j<=i;j++){
        if(j==0) c[i][j]=1;
        else   c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

但是本题n的范围达到了$2\times 10^3$ 。会超出long long数据范围。并且，每次得到范围n和m之后，需要遍历$C_0^0\sim C_n^m$ 统计能整除k的元素个数。重复t次，整体复杂度为$O(t· n· m)$ ，会超时。

此时需要解决两个问题：

范围过大导致答案错误
重复遍历，时间超时

对于问题1：

再来看数太大的问题，根据组合数的性质：$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$ ,且我们只需要统计能否整除k的个数，那么利用同余性质，C[i][j]中存放$C_n^m\% k$ 的结果即可。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=2e3+5;
typedef long long ll;
ll c[N][N];
ll sum[N][N];
int main(){
    int t,k;
    int n,m;
    cin>>t>>k;
    c[0][0]=c[1][0]=c[1][1]=1%k;
    for(int i=2;i<=N-5;i++){
        for(int j=0;j<=i;j++){
            c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;
        }
    }
    
    while(t--){
        cin>>n>>m;
        int cnt=0;
        for(int i=1;i<=n;i++){
            int M=min(i,m);
            for(int j=0;j<=M;j++){
                if(c[i][j]==0) cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

再来解决超时问题。

$C_0^0\sim C_n^n$ 的所有值都是固定的，每次遍历$C_0^0\sim C_n^m$ 统计的话，很多都是重复统计了。此时可以利用前缀和提前统计区间内的满足的总和。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N=2e3+5;
typedef long long ll;
ll c[N][N];//c[i][j]为C(i,j)%k
ll s[N][N];//s[i][j]为c(i,0)~c(i,j)的能整除k的元素总数
int main(){
    int t,k;
    int n,m;
    cin>>t>>k;
    //预处理 c[i][j] 为C[i][j]%k
    //C(i,j)=C(i-1,j)+C(i-1,j-1)
    c[0][0]=c[1][0]=c[1][1]=1%k;
    for(int i=2;i<=N-5;i++){
        for(int j=0;j<=i;j++){
            if(j==0) c[i][j]=1%k;
            else c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;
        }
    }
    for(int i=0;i<=N-5;i++){
        for(int j=0;j<=i;j++){
            if(j==0) s[i][j]=!c[i][j];
            else s[i][j]=s[i][j-1]+!c[i][j];
        }
    }
    
    while(t--){
        cin>>n>>m;
        ll sum=0;//满足条件的总数
        if(m>n){
            m=n;
        } 
        for(int i=0;i<=n;i++){
            sum+=s[i][min(i,m)];
        }
        cout<<sum<<endl;
    }
    return 0;
}

组合数问题