题解 008 题目 P2822

array2022 · 2025-01-04 18:13:49 · 题解

题目分析

• 数据范围中提到 0\le n,m \le 2\times 10^3，因此可以想到可以使用组合数递推式 \tbinom{n}{m}=\tbinom{n-1}{m-1}+\tbinom{n-1}{m} 进行预处理，时间复杂度 O(nm)。
• 对于每次询问，如果暴力查找的话时间复杂度为 O(nm)，只能拿到部分分数。由于每次询问的 k 都一样，还是访问子矩阵，可以考虑二维前缀和。如果 k\mid\tbinom{n}{m}，设矩阵 x 的 x_{n,m} 为 1，否则为 0，每次询问输出 x 前缀和即可。时间复杂度 O(1)。

通过代码

#include<iostream>
using namespace std;
int t,k,n,m,c[2005][2005],x[2005][2005],a[2005][2005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t>>k;
    for (int i=0;i<=2000;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]%k+c[i-1][j]%k)%k; // 记得取模。
            if (c[i][j]==0) x[i][j]+=1; // 如果 c[i][j] 整除 k，将 x[i][j] 记为 1，查询时输出它的前缀和。
        }
    } // 预处理，注意边界情况。
    for (int i=0;i<=2000;i++){
        for (int j=0;j<=2000;j++){
            if (i>0&&j>0) a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+x[i][j];
            else if (i>0&&j==0) a[i][j]=a[i-1][j]+x[i][j];
            else if (i==0&&j>0) a[i][j]=a[i][j-1]+x[i][j];
            else a[i][j]=x[i][j];
        }
    } // 计算 x 数组的前缀和，同样记得注意边界情况。
    while (t--){
        cin>>n>>m;
        cout<<a[n][m]<<"\n";
    } // 每次访问，输出前缀和。
    return 0;
}