题解：[P2822 组合数问题

· · 题解

题目传送门：P2822 [NOIP2016 提高组] 组合数问题

这篇记叙文题解将带大家回顾蒟到极致的作者集训做这题的心路历程。

我将尝试把绝大多数“我们”改成“我”。

Part 1 遇事不决打暴力

本题的暴力十分显然。我先写一个组合数函数。

long long C(int n,int m){
    long long s=1;
    for(long long i=n-m+1;i<=n;i++)s*=i;
    for(long long i=1;i<=m;i++)s/=i;
    return s;
}

（可能大家在实现的细节上不尽相同，但都大同小异）

int main(){
    cin>>t>>k;
    while(t--){
        int ans=0;
        cin>>n>>m;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=min(i,m);j++)
                ans+=(C(i,j)%k==0);
        cout<<ans<<'\n';
    }
    return 0;
}

得分：45pts。

Part 2 推个柿子优个化

我经过简单的推式子，发现：

\binom{n}{m+1}=\frac{n!}{(m+1)!(n-m-1)!}=\frac{n!}{m!(n-m)!}\cdot \frac{n-m}{m+1}

于是我把组合数函数删了。毕竟那玩意时间复杂度太高。

int main(){
    cin>>t>>k;
    while(t--){
        int ans=0;
        cin>>n>>m;
        for(int i=0;i<=n;i++){
            long long a=C(i,0);
            for(int j=0;j<=min(i,m);j++){
                ans+=(a%k==0);
                //ans+=(C(i,j)%k==0);
                a=a*(i-j)/(j+1);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

得分：60pts。

Part 3 山重水复疑无路，杨辉三角启动

接下来不好优化了，于是我听到老师讲杨辉三角。

众所周知杨辉三角表现在二维数组里就是 f_{i,j}=f_{i-1,j-1}+f_{i-1,j}。

而众所又周知：

\begin{aligned} &\binom{n-1}{m-1}+\binom{n-1}{m}\\ \\=&\frac{(n-1)!}{(m-1)![(n-1)-(m-1)]!}+\frac{(n-1)!}{m![(n-1)-m]!}\\ \\ =&\frac{(n-1)!m}{m!(n-m)!}+\frac{(n-1)!(n-m)}{m!(n-m)!}\\ \\ =&\frac{(n-1)!(m+n-m)}{m!(n-m)!}\\ \\ =&\frac{n!}{m!(n-m)!}\\ \\ =&\binom{n}{m} \end{aligned}

所以组合数可以直接用杨辉三角来推。我一看数据范围：诶，2\times 10^3，这不正好开二维数组吗！而之前会爆 long long 却无计可施的原因是除法不能取模，现在变成加法就可以了啊！而我只关心它模 k 的余数。于是：

using namespace std;
const int MAXN=2000;
int t,n,m;
long long k;
int C[2003][2003];
int main(){
    cin>>t>>k;
    for(int i=0;i<=MAXN;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
        }
    }
    while(t--){
        int ans=0;
        cin>>n>>m;
        for(int i=0;i<=n;i++){
            int mn=min(i,m);
            for(int j=0;j<=mn;j++){
                ans+=(C[i][j]%k==0);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

得分：90pts。

剩下的两个点 TLE 了，我只能在循环内部优化了。

Part 4 二维前缀和加持，所向披靡！

我发现，每次求的东西都是从 0 遍历到 n，然后每维再从 0 遍历，这样求一个二维相邻部分的状态和。所以可以很容易地使用二维前缀和优化。

#include<iostream>
using namespace std;
const int N=2000;
int t,n,m,k;
int C[2003][2003];//杨辉三角
int d[2003][2003];//前缀和
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);  
    cin>>t>>k;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
        }
    }
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            if(j<=i)d[i][j]=d[i-1][j]-d[i-1][j-1]+d[i][j-1]+(C[i][j]%k==0);//二维前缀和的式子
            else d[i][j]=d[i][i];//杨辉三角的空白部分要填充上
        }
    }
    while(t--){
        cin>>n>>m;
        cout<<d[n][min(n,m)]<<'\n';//答案
    }
    return 0;
}

得分：100pts。