P2822 [NOIP2016 提高组] 组合数问题 题解

· · 题解

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

原文，但是被拒了。

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

而众所又周知：

\begin{equation} \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} \end{equation}

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

const int MAXN=2000;
int t,n,m;
long long k;
int C[2003][2003];//存 C(n,m) 模 k 后的余数
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 了。

我发现，每次求的东西都是从 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。