ZOJ 3624 Count Path Pair 排列组合
2024-08-30 05:08:35
思路:在没有限制条件时,很容易知道结果为C(m+n,n)*C(m+q-p,q).
然后再把相交的情况去除就可以了。而如果想到了就是水题了……
求A->D,B->C相交的情况可以转化为求A->C,B->D的情况。
所以结果就为C(m+n,n)*C(m+q-p,q)-C(m+q,m)*C(m+n-p,n).
代码:
#include<cstdio>
#include<algorithm>
#define M 200001
#define mod 100000007
#define ll long long
using namespace std;
ll inv(ll x)
{
if(x==) return ;
return inv(mod%x)*(mod-mod/x)%mod;
}
ll C(ll a,ll b)
{
ll u=,v=,i,t;
t=max(b,a-b);
for(i=;i<t;i++){
u=u*(a-i)%mod;
v=v*(i+)%mod;
}
return u*inv(v)%mod;
}
int main()
{
ll m,n,q,p;
while(scanf("%lld%lld%lld%lld",&m,&n,&p,&q)!=EOF){
ll ans=C(m+n,m)*C(m+q-p,q)%mod-C(m+q,m)*C(m+n-p,n)%mod;
if(ans<) ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
return ;
}
最新文章
- Objective-C 工厂模式(上) -- 简单工厂模式
- 下载Orchard源码
- JavaScript学习笔记-元素在滚动条滑动一定高度后自动置顶
- android布局学习-使用FrameLayout和LinearLayout制作QQ空间底部导航栏
- iOS开发之网络数据解析(二)--XML解析简介
- Android-xUtils框架介绍(二)
- ELK Packetbeat 部署指南(15th)
- Winform 隐藏程序窗口
- gitosis使用笔记
- [Python笔记][第三章Python选择与循环]
- [LeetCode]题解(python):013-Roman to Integer
- 从Unity中的Attribute到AOP(八)
- dev和master合并冲突解决
- Jenkins的安装配置和使用
- ECShop全系列版本远程代码执行高危漏洞分析+实战提权
- mysql load_file在数据库注入中使用
- 大道至简第一章Java伪代码
- C# RabbitMQ延迟队列功能实战项目演练
- 谷歌发布了 T2T(Tensor2Tensor)深度学习开源系统
- leetcode - [6]Binary Tree Postorder Traversal
热门文章
- 导航狗IT周报-2018年05月27日
- c++中指针常量,常指针,指向常量的常指针区分
- python基础===string模块常量
- 017 CPU冲高定位方法
- 安装 Xamarin for Visual Studio
- 以应用带动SDN发展(CDN峰会 工信部杨崑)(转)
- Shp上传至Oracle Spatial
- Char 与 Byte
- csu 1749: Soldiers &#39; Training(贪心)
- 【hdoj_1753】大明A+B(大数)