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 ;
}