bzoj 2982 combination——lucas模板
2024-08-27 03:56:11
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2982
明明是lucas定理裸题……
非常需要注意C( )里 if ( n<m ) return 0; !!!!!
可以预处理阶乘和其逆元,也可以现求。现求阶乘逆元的话,可以把 jc[m] 和 jc[n-m] 乘起来再放到pw里。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=;
int T,n,m,jc[mod+],ans;
int pw(int x,int k)
{
int ret=;while(k){if(k&)(ret*=x)%=mod;x=(ll)x*x%mod;k>>=;}return ret;
}
void init()
{
jc[]=;
for(int i=;i<mod;i++)jc[i]=jc[i-]*i%mod;
}
int C(int n,int m)
{
if(n<m)return ;//
return (ll)jc[n]*pw(jc[m]*jc[n-m],mod-)%mod;//jc[m]*jc[n-m]一起求逆元
}
int lucas(int n,int m)
{
if(!m)return ;
if(n<mod&&m<mod)return C(n,m);
return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
printf("%d\n",lucas(n,m));
}
return ;
}
现求阶乘逆元
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=;
ll n,m;
int T,jc[mod+],jcn[mod+],ans;
int pw(int x,int k)
{
int ret=;while(k){if(k&)(ret*=x)%=mod;(x*=x)%=mod;k>>=;}return ret;
}
void init()
{
jc[]=;
for(int i=;i<mod;i++)jc[i]=jc[i-]*i%mod;
jcn[mod-]=pw(jc[mod-],mod-);
for(int i=mod-;i>=;i--)jcn[i]=jcn[i+]*(i+)%mod;
}
int C(int n,int m)
{
if(n<m)return ;////
return jc[n]*jcn[m]%mod*jcn[n-m]%mod;
}
int lucas(ll n,ll m)
{
if(!m)return ;
if(n<mod&&m<mod)return C(n,m);
return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
printf("%d\n",lucas(n,m));
}
return ;
}
最新文章
- 在ASP.NET Core应用中如何设置和获取与执行环境相关的信息?
- WCF调用
- 新版 itextsharp pdf code
- Linux指令小结
- delayed ack与nagle&#39;s算法
- C#Light Unity逻辑热更新解决方案0.20 发布
- 微信公众平台中添加qq在线聊天代码
- Delphi 中的 procedure of object
- 使用 Delphi Xe 的 TDictionary
- SVN服务器几种备份策略---重点svnsync备份---OK
- 关于IIS部署成功后,局域网其他用户无法访问的问题解决方法
- 一类斜率优化的dp(特有性质:只能连续,不能交叉)
- 网页头部 lang的声明
- 【Javascript】JS的异步操作,浏览器的多线程间的协作
- web程序顺序
- GitHub入门与实践 读书笔记三:(1)GitHub账户注册教程
- Docker2之Service
- VS版本号定义、规则和相关的Visual Studio插件
- Python通过LDAP验证、查找用户(class,logging)
- linux 查找文件命令