Luogu P1641 [SCOI2010]生成字符串 组合数学
2024-09-05 06:59:45
神仙。。。。
当时以为是,$x$代表$1$,$y$代表$0$,所以不能过$y=x$的路径数。。。结果不会。。。
然后康题解。。。ヾ(。`Д´。)竟然向右上是$1$,向右下是$0$。。。。
所以现在就是不能过$y=-1$;
所以我们可以这样想:如果有非法路径的话,那么就把他第一次与$y=-1$交点与起点之间的路径沿$y=-1$翻转;
然后现在非法路径的条数就是从$(0,-2)$到$(n+m,n-m)$路径数量,把他拿所有路径的减掉就行了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define R register int
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
const int M=;
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int fac[M];
inline ll Inv(ll x) {
if(x==) return ; if(x<=) return ; return (M-M/x*Inv(M%x)%M)%M;
}
inline ll C(ll n,ll m) {
if(n<m) return ; return (ll)fac[n]*Inv((ll)fac[n-m]*fac[m]%M)%M;
} ll n,m;
signed main() {
#ifdef JACK
freopen("NOIPAK++.in","r",stdin);
#endif
n=g(),m=g();
fac[]=fac[]=; for(R i=;i<n+m;++i) fac[i]=(ll)fac[i-]*i%M;
printf("%lld\n",(C(n+m,n)-C(n+m,n+)+M)%M);
}
2019.06.05
最新文章
- 基础篇-struts2的搭建
- [转][MVC] 剖析 NopCommerce 的 Theme 机制
- Android studio的深坑 导jar包重复的异常处理
- ServletDemo
- Python3基础 len函数 获得一个字符串的字符个数
- bloom filter 详解[转]
- lightoj1057 - Collecting Gold (tsp问题)
- NSURLConnection下载
- 移动端h5摇一摇事件
- js apply 和call的区别
- C#7的9个新语法
- 开源框架GreenDao的操作
- MySQL中索引的基础知识
- java什么叫线程安全?什么叫不安全?
- hexo next主题为博客添加分享功能
- 谈谈MySQL的事务隔离级别
- 【一天一道LeetCode】#258. Add Digits
- Java基础12:深入理解Class类和Object类
- js判断是否是移动端自动跳转到wap页面代码
- waf python build 工具使用流程
热门文章
- Centos安装elasticsearch,php连接使用
- C库函数:scanf、fscanf、printf、fprintf、sprintf、 snprintf
- Spring Boot Redis 集成 Error creating bean with name &#39;enableRedisKeyspaceNotificationsInitializer&#39;
- StoneTab标签页CAD插件 3.2.0
- c# 自定义解析JSON字符串数据
- 【原创】大叔经验分享(78)hive查询报错NoViableAltException
- Eclipse 动态添加web.xml
- 13 Msql之四种事务隔离界别
- kalilinux 渗透测试笔记
- 【python+selenium】selenium grid(分布式)