[noip2016]组合数问题<dp+杨辉三角>

题目链接：https://vijos.org/p/2006

当时在考场上只想到了暴力的做法，现在自己看了以后还是没思路，最后看大佬说的杨辉三角才懂这题。。。

我自己总结了一下，我不能反应出杨辉三角的递推是因为对组合C和排列S不熟悉导致的，这些公式基本都是我的短板

从杨辉三角形看出，杨辉三角的i，j位（有0位）就是在i个数选j个出来的方案数，，我们来看下杨辉三角吧

------------------------------------------------------------------------------------------------------------------------------

1　　1

1　　2　　1

1　　3　　3　　1

1　　4　　6　　4　　1

1　　5　　10　 10　 5　　1

1　　6　　15　 20　 15　 6　　1

………………………………………………

--------------------------------------------------------------------------------------------------------------------------------

只需要赋初值最上面那个a[0][0]为1就可以预处理出这个2000*2000的图了。。。。

输入n，m只需要判断0<=i<=n和0<=j<=min(n,m)的所有数是不是k的倍数，这个来源就是n,m的左方和上方的数，用以n,m为原点的坐标系说就是第二象限的值，包括x负半轴y正半轴

所以维护一个line[j]表示到当前为止，第j列有几个是k的倍数，然后就是自己这列的个数加上num[i-1][j]

num[i][j]=num[i-1][j]+line[j]

然后就可以愉快的做这道题了，最后提醒一点

所有的杨辉三角的值对k取个模，因为我们只是找k个倍数

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<iostream>

 #include<cstdlib>

 #define maxn 2005

 using namespace std;

 int t,k,a[maxn][maxn];

 int num[maxn][maxn];

 int n,m,line[maxn];

 void show(int x){

     for(int i=;i<=x;i++){

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

             printf("%d ",a[i][j]);

         }

         printf("\n");

     }

 }

 void show2(int x){

     for(int i=;i<=x;i++){

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

             printf("%d ",num[i][j]);

         }

         printf("\n");

     }

 }

 int main(){

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

         a[i][]=;

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

     for(int i=;i<=;i++){

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

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

             int look=a[i][j];

             if(a[i][j]==){//是k倍数

                 line[j]++;

             }

             num[i][j]=num[i][j-]+line[j];

         }

     }

 //    show(6);

 //    show2(6);

     for(int i=;i<=t;i++){

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

          m=min(m,n);

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

     }

 //show函数只是用来输出这个表，看下有没有误而已，可以删去

 }

总结：很多一看就知道爆数组爆longlong的题，把结果用表格对应写出来，说不定会有意想不到的惊喜

巴特西

[noip2016]组合数问题<dp+杨辉三角>

最新文章

热门文章