预处理组合数
基本做法
针对大多数仅仅是利用组合数求解问题的题目运用递推法打表，不仅方便，而且可以稳稳地控制复杂度，对于需要多次引用组合数的题目效果极佳：
基于组合数公理性质：
\[C^m_n=C^{n-m}_n
\]
推得：
\[C^m_n=C^{m-1}_{n-1}+C^m_{n-1}
\]
由这个递推公式就可以熟练的写出组合数代码，但要注意初始化:
\[C^0_0=0
\]
\[C^i_0=C^1_0=C^1_1=1
\]
同时，把表打出来后，我们会发现这就是杨辉三角，这个三角可以解决很多问题，记住打印三角的方法也可以打出组合数。
inline void build()
{
c[0][0]=1;
c[1][0]=c[1][1]=1;//如上初始化，绝对绝对不能忘记或错，结合常识。
for(int i=2;i<=2000;i++)
{
c[i][0]=1;
for(int j=1;j<=2000;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];//递推公式。
}
}
例题
这题还需要再用前缀和来优化查询速度
前缀和可以有效减少查询统计时的复杂度，每一次查询\(O(n)\)降到\(O(1)\)
记住：上加左 减左上 加自己
\(ans[i][j]=ans[i][j-1]+ans[i-1][j]-ans[i-1][j-1]\)
inline void build()
{
c[0][0]=1;
c[1][0]=c[1][1]=1;
for(int i=2;i<=2000;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];//前缀和。
if(!c[i][j])ans[i][j]++;//如果满足结论，计数加一。
}
ans[i][i+1]=ans[i][i];//继承。
}
}
inline void solve()
{
t=read(),k=read();
build();
while(t--)
{
n=read(),m=read();
if(m>n)printf("%lld\n",ans[n][n]);//如果m>n,ans只会达到n，只需输出ans[n,n]就可以了。
else printf("%lld\n",ans[n][m]);
}
}
总结
- 需掌握组合数的基本两种求解方法(通项公式，递推公式），根据数据范围选定方法。
- 结合数据范围找到优化方法，无论是取模还是自己的玄学优化都尝试一下.(建议取模输出的题，绝对不要乱模！既费时又易错)
- 掌握前缀和，利用前缀和对降维的作用。