洛谷P2822 组合数问题（题解）

https://www.luogu.org/problemnew/show/P2822（题目传送）

先了解一下有关组合数的公式：（m在上，n在下）

组合数通项公式：C（n,m）=n!/[m!(n-m)!]=(n-m+1)!/m!

组合数递推公式：C（n,m）=C(n-1,m-1)+C(n-1,m)

发现组合数的递推的直观图像形式就是杨辉三角（第i行第j列的数等于C（i-1,j-1））

由于题目要求多组组合数，便可以递推组合数做预处理（直接用通项公式算什么的太粗暴（慢）了）。一看数据范围，保证让普通范围溢出的节奏啊，但定心一看，我们只用知道每个组合数是否能整除k就可，所以可以每次递推算组合数时模k。　　TIP：递推不要忘了初始状态（边界）

求出组合数后，发现如果对每次询问都从头到尾扫一遍的话保准会超时，便想到了一个能有效减少查询统计时的复杂度，每一次查询O(n)降到O(1)的神器——前缀和。求一个矩阵的前缀和，只要记住公式：上加左，减上左，加自己。

AC代码如下：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int c[][],n[],m[],dp[][];

 int main()

 {

     int t,k,mmax=,nmax=;

     cin>>t>>k;

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

     {

         scanf("%d%d",&n[i],&m[i]);

         if(nmax<n[i]) nmax=n[i];

         if(mmax<m[i]) mmax=m[i];

     }

     c[][]=;

     int mmaxb=mmax;

     if(mmax>nmax) mmax=nmax+;

     else mmax++;

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

         for(int j=;j<=min(i,mmax);j++)

         {

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

             if(!c[i][j]) dp[i-][j-]=;

         }//这里用杨辉三角递推的组合数，***需要多做一行***，其实没有直接推组合数方便。

     for(int j=;j<=mmaxb;j++) dp[][j]+=dp[][j-];

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

         for(int j=;j<=mmaxb;j++)

         {

             if(!j) dp[i][j]+=dp[i-][j];

             else

                 dp[i][j]+=dp[i-][j]+dp[i][j-]-dp[i-][j-];

         }

     for(int i=;i<=t;i++) cout<<dp[n[i]][m[i]]<<endl;

     return ;

 }

巴特西

洛谷P2822 组合数问题（题解）

组合数通项公式：C（n,m）=n!/[m!(n-m)!]=(n-m+1)!/m!

组合数递推公式：C（n,m）=C(n-1,m-1)+C(n-1,m)

最新文章

热门文章