AcWing 885 求组合数 I
发布日期:2021-05-28 16:27:09 浏览次数:9 分类:技术文章

本文共 916 字,大约阅读时间需要 3 分钟。

题目描述:

给定n组询问,每组询问给定两个整数a,b,请你输出C(a,b) mod (10^9+7)的值。

输入格式

第一行包含整数n。接下来n行,每行包含一组a和b。

输出格式

共n行,每行输出一个询问的解。

数据范围

1≤n≤10000,1≤b≤a≤2000

输入样例:

33 15 32 2

输出样例:

3101

 分析:

本题b和a的范围均不超过2000,故我们可以预处理出所有组合数的值,一个1 + 2 +...+2000 = 1000 * 2001约等于两百万,故可以在一秒内计算完成。具体的求法利用了组合数的递推式C(n,m) = C(n - 1,m) + C(n - 1,m - 1)。该递推式的推导使用的是类似于dp的思想,C(n,m)表示在n个物品中选出m个物品的选法,可以划分为两种情况,第一种情况是m个物品均来自前n-1个物品,一共C(n-1,m)中选法;第二种情况是m - 1个物品来自前n - 1个物品,最后一个物品来自第n个物品,一共C(n-1,m-1)种选法,故可以得到C(n,m) = C(n - 1,m) + C(n - 1,m - 1)。边界情况为一个都不选的情况,方案数为1。

#include 
using namespace std;const int maxn = 2005,mod = 1e9 + 7;int c[maxn][maxn];int main(){ int n,a,b; scanf("%d",&n); for(int i = 0;i <= 2000;i++){ for(int j = 0;j <= i;j++){ if(!j) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } } while(n--){ scanf("%d%d",&a,&b); printf("%d\n",c[a][b]); } return 0;}

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/103795459 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 886 求组合数 II
下一篇:AcWing 884 高斯消元解异或线性方程组

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年02月06日 05时08分31秒