AcWing - 求组合数 II(预处理&逆元)
发布日期:2021-07-01 00:21:41
浏览次数:3
分类:技术文章
本文共 1081 字,大约阅读时间需要 3 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
给定n组询问,每组询问给定两个整数a,b,请你输出的值。
输入格式
第一行包含整数n。
接下来n行,每行包含一组a和b。
输出格式
共n行,每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤10^5
输入样例
3
3 1 5 3 2 2
输出样例
3
10 1
解题思路
题意:求出的值。
思路:范围小的话可以通过递推求出,否则就要先预处理。首先预处理出所有阶乘取模的余数fact[N],以及所有阶乘取模的逆元infact[N],如果取模的数是质数,可以用费马小定理求逆元。由,我们可以令,,则。
Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 1e5, MAXM = 1e5 + 5;const int MOD = 1e9 + 7;int fact[MAXM], infact[MAXM];int Fast_Power(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; } return res;}void Com_Num(int n) { fact[0] = infact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = 1ll * fact[i - 1] * i % MOD; infact[i] = 1ll * infact[i - 1] * Fast_Power(i, MOD - 2, MOD) % MOD; }}int main() { int t; Com_Num(MAXN); scanf("%d", &t); while (t--) { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", 1ll * fact[a] * infact[b] % MOD * infact[a - b] % MOD); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99707410 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月10日 04时24分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
flex4 datagrid增加链接按钮的方法实现
2021-07-04
flex4取得datagrid里字段值的正确方法
2021-07-04
flex4 datagrid里点击链接打开图片的方法
2021-07-04
flex4 无法编译生成html解决办法
2021-07-04
flex4 日期选择器实现 2022-12-20样式的功能
2021-07-04
mysql linux 下表名忽略大小写相关设置
2021-07-04
单态设计模式
2021-07-04
如何破解Flex4序列号失效问题
2021-07-04
最优化的ms sql server分页sql语句
2021-07-04
在java语言计算数据库记录总数的简便算法
2021-07-04
JS操作JSON总结
2021-07-04
用img标签实现数据提交
2021-07-04
关于sql中日期相关跨年处理
2021-07-04
同步/异步 阻塞/非阻塞 .
2021-07-04
resin配置jndi数据源-sql server2008
2021-07-04
关于webwork+freemarker的简单实例
2021-07-04
关于phprpc测试实例
2021-07-04
关于二进制Web服务框架Hessian最简单代码实例
2021-07-04
在jsp获取客户端的IP地址工具方法
2021-07-04
关于struts1.3中使用DispatchAction的一个问题
2021-07-04