CJOJ 2255 【NOIP2016】组合数问题 / Luogu 2822 组合数问题 （递推）
Description
组合数\[C^m_n\]表示的是从n个物品中选出m个物品的方案数。举个例子，从（1,2,3) 三个物品中选择两个物品可以有（1,2),(1,3),(2,3)这三种选择方法。根据组合数的定 义，我们可以给出计算组合数的一般公式：\[C^m_n=\frac{n!}{m!(n-m)!}\] 其中n! = 1 × 2 × · · · × n
小葱想知道如果给定n,m和k，对于所有的0 <= i <= n，0 <= j <= min(i,m)有多少对 (i,j)满足是k的倍数。
第一行有两个整数t,k，其中t代表该测试点总共有多少组测试数据。
接下来t行每行两个整数n,m。
Output
t行，每行一个整数代表答案。
1 2 3 3
Sample Output
1
Http
Luogu:https://www.luogu.org/problem/show?pid=2822 CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2255
Source
递推
解决思路
不要被题目给出的那个式子给迷惑了！要是真按照那么算，肯定会爆掉！ 这道题我们可以离线地来做。我们知道，计算组合数除了上面题目中给出的通项式之外，还有一个递推式：\[C^m_n=C^{m-1}_{n}+C^{m-1}_{n-1}\] 那么我们可以开一个二维数组存下所有的组合数（题目范围只有2000嘛）。至于是否整除的问题，我们可以在每一步计算的时候%k，这样既保证了不会爆掉long long 又能求出是否整除（若最后算出来是0就是可以整除啦）。
我们再把能整除的置为1，不能整除的置为0，求一下二维前缀和，然后就可以O(1)地回答询问啦。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxN=2000;
const int inf=2147483647;
int n,m,mod;
int C[maxN+10][maxN+10];
int If[maxN+10][maxN+10];
int main()
{
int TT;
cin>>TT>>mod;
memset(C,0,sizeof(C));
for (int i=0;i<=maxN;i++)//递推算出所有的组合数并取膜
{
C[i][0]=1;
for (int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for (int i=0;i<=maxN;i++)
for (int j=0;j<=i;j++)//构造二维前缀和初值
If[i][j]=(bool)(C[i][j])^1;
/*for (int i=0;i<=10;i++)
{
for (int j=0;j<=10;j++)
cout<<If[i][j]<<' ';
cout<<endl;
}
cout<<endl;*/
for (int i=1;i<=maxN;i++)//计算二维前缀和
for (int j=1;j<=maxN;j++)
If[i][j]=If[i][j]+If[i-1][j]+If[i][j-1]-If[i-1][j-1];
/*for (int i=0;i<=10;i++)
{
for (int j=0;j<=10;j++)
cout<<If[i][j]<<' ';
cout<<endl;
}
cout<<endl;*/
for (int ti=1;ti<=TT;ti++)//回答询问
{
cin>>n>>m;
cout<<If[n][m]<<endl;
}
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7171502.html
相关资源：JAVA上百实例源码以及开源项目
