洛谷P2822 组合数问题杨辉三角

没想到这道题竟然这么水…

我们发现m,n都非常小，完全可以O(nm)O(nm)O(nm)预处理出stripe数组，即代表(i,j)(i,j)(i,j)

及其向上的一列的个数，然后进行递推即可。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 2003;

int C[maxn][maxn];

int ans[maxn][maxn], stripe[maxn][maxn];

int main()

{

  //froepen("in.txt","r",stdin);

    int T,k;

    scanf("%d%d",&T,&k);

    for(int i = 1;i <= 2001; ++i) C[i][i] = C[i][0] = 1;

    for(int i = 1;i <= 2001; ++i)

        for(int j = 1;j < i; ++j)

            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % k;

    for(int i = 2;i <= 2001; ++i)

        for(int j = 0;j <= i; ++j)

        {

            if(C[i][j] == 0) ans[i][j] = stripe[i][j] = 1;

            stripe[i][j] += stripe[i-1][j];

            ans[i][j] += stripe[i-1][j];

            if(j > 0) ans[i][j] += ans[i][j-1];

        }

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        m = min(m,n);

        printf("%d\n",ans[n][m]);

    }

    return 0;

}

巴特西

洛谷P2822 组合数问题杨辉三角

最新文章

热门文章

巴特西

洛谷P2822 组合数问题 杨辉三角

最新文章

热门文章

洛谷P2822 组合数问题杨辉三角