HDU 3398 String
2024-10-14 13:44:25
题目大意:一个长为n的01字符串,使前缀任意0的数量不大于1的数量,求方案数……
题解:高一模拟赛时做过,是卡特兰数的几何意义,将字符串变为矩阵寻路,不可越过对角线,那么就是卡特兰数了,C(n+m, n)-C(n+m,n+1)=(n+1-m)(n+m)!/(n+1)!m!。需要注意的是取模的问题,如果用高精度最后取模会太慢了,会超时,所以直接用power定理分解素数,对于每个素数分别算幂,取模相乘即可。
#include <cstdio>
#include <cstring>
const int N=1000001;
using namespace std;
typedef long long LL;
int pri[N*2+1],p[N*2+1],tot;
int cal(int pr,int n){int rs=0;while(n)n/=pr,rs+=n;return rs;}
void initp(){
memset(pri,0,sizeof pri); tot=0;
for(int i=2;i<=N*2;i++){
if(pri[i])continue; p[tot++]=i;
for(int j=i*2;j<=N*2;j+=i)pri[j]=1;
}
}
int main(){
int cas,n,m; initp();
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
LL rs=1; int nm=n-m+1;
for(int i=0;i<tot&&p[i]<=n+m;i++){
int cnt=0;
while(nm%p[i]==0)nm/=p[i],cnt++;
int ipow=cnt+cal(p[i],n+m)-cal(p[i],n+1)-cal(p[i],m);
for(int j=1;j<=ipow;j++){
rs=(rs*p[i])%20100501;
}
}
printf("%lld\n",rs);
}
return 0;
}
最新文章
- 使用jQuery要注意的问题
- action属性
- 进入名企必读的.NET面试题
- tcpprep 对IPV6的支持
- 【Android开发】完美解决Android完全退出程序
- Html5 布局经验分享-第1集
- Linux 共享内存编程
- 在C#中internal关键字是什么意思?和protected internal区别
- Paper.js - Paper.js
- Git 使用规范流程(转)
- .net cookie
- 【java】内存流:java.io.ByteArrayInputStream、java.io.ByteArrayOutputStream、java.io.CharArrayReader、java.io.CharArrayWriter
- html静态页面乱码
- springBoot总结
- liunx安装py.27
- dpdk环境配置
- 20165313 《Java程序设计》第七周学习总结
- POJ2485:Highways(模板题)
- iOS 中的 armv7,armv7s,arm64,i386,x86_64 都是什么
- 设置jQuery validate插件错误提示位置