Codeforces 57C (1-n递增方案数,组合数取模,lucas)
2024-10-21 06:47:42
这个题相当于求从1-n的递增方案数,为C(2*n-1,n);
取模要用lucas定理,附上代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mod=1000000007;
LL quick_mod(LL a,LL b){
LL ans=1%mod;
while(b){
if(b&1){
ans=ans*a%mod;
b--;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
LL C(LL n,LL m){
if(m>n)return 0;
LL ans=1;
for(int i=1;i<=m;i++){
LL a=(n+i-m)%mod;
LL b=i%mod;
ans=ans*(a*quick_mod(b,mod-2)%mod)%mod;
}
return ans;
}
LL lucas(LL n,LL m){
if(m==0)return 1;
return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main(){
LL a,ans;
scanf("%lld",&a);
ans=(2*lucas(a*2-1,a)%mod-a+mod)%mod;
printf("%lld\n",ans);
}
最新文章
- (C++)窗口置前SetForegroundWindow(pThis->;hwndWindow);
- jquery 之ajax获取数据
- Project和Module的介绍
- Eclipse Android HH and theme
- Python学习笔记捌——面向对象高级编程
- php中常用的处理字符串的函数
- SICP-1.7-递归函数
- python-opencv在有噪音的情况下提取图像的轮廓
- UVA - 1592 Database 枚举+map
- NGINX详解
- vs2013中集成Git
- Confluence 6 针对 &#39;unmigrated-wiki-markup&#39; 宏重新尝试合并
- C 标准库头文件
- Gym 101873D - Pants On Fire - [warshall算法求传递闭包]
- CEO退休
- PHP实现IP访问限制及提交次数的方法详解
- SecureCRT显示乱码的解决办法
- DocumentManager 在标签位置显示气泡框 z
- 卸载Linux自带的JDK
- c++动态库封装及调用(2、windows下动态库创建)
热门文章
- Java map简介
- 计算客网络赛 Coin 二项式定理+逆元
- vue项目中如何将工具函数模块化导出
- Spring_总结_03_装配Bean(一)_自动装配
- 源码编译安装mysql5.6
- spring MVC HandlerInterceptorAdapter
- HDU - 5412 CRB and Queries (整体二分)
- Java操作Redis(代码演示)
- mysql_union all 纵向合并建表_20170123
- SQL夯实基础(一):inner join、outer join和cross join的区别