首先,从$(0,0)$走到$(n,m)$的方案数是$ C_{n+m}^n$,可以把走的方向看作一种序列,这个序列长$ n+m$ ,你需要从中任取$n$个位置,让他向右走;

然后就是如何处理不能走的点:把点sort一遍,按横纵坐标降序排列,这样前面的点可能会包含后面的点,所以算方案数时时要考虑。

算出来从$(0,0)$到$橙色的点(x,y)$的方案数为$C_{x+y}^x$,再减去蓝色点*蓝色点到橙色点方案数,才是到橙色点的方案数;

注意每条非法路径只会被第一个经过他的非法的点记录。

在最后把每个店的方案数再乘上到终点的代价,就是在模其中一个数意义下的解;

最最后用中国剩余定理合并。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define R register ll
using namespace std;
inline ll 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;
}
struct node {int x,y;
bool operator <(const node& b) const{return x==b.x?y<b.y:x<b.x;}
} a[];
ll f[],p[],ans[],M[],T[];
ll fac[],inv[];
inline ll C(ll n,ll m,ll p) {
if(n<m) return ; return fac[n]*inv[fac[m]*fac[n-m]%p]%p;
}
inline ll L(ll n,ll m,ll p) {
if(n<m) return ; if(!n) return ;
return L(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
ll n,m,t,mod,tot,S=;
signed main() {
n=g(),m=g(),t=g(),mod=g();
if(mod==) p[++tot]=mod;
else p[]=,p[]=,p[]=,p[]=,tot=;
for(R i=;i<=t;++i) a[i].x=g(),a[i].y=g();
sort(a+,a+t+); for(R i=;i<=tot;++i) S*=p[i];
for(R i=;i<=tot;++i) M[i]=S/p[i]; inv[]=,fac[]=;
for(R k=;k<=tot;++k) {
R P=p[k]; for(R i=;i<P;++i) inv[i]=(P-P/i*inv[P%i]%P)%P;
T[k]=inv[M[k]%P]; for(R i=;i<P;++i) fac[i]=fac[i-]*i%P;
ans[k]=L(n+m,n,P); for(R i=;i<=t;++i) {
f[i]=L(a[i].x+a[i].y,a[i].x,P);
for(R j=;j<i;++j) if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
f[i]+=(P-f[j]*L(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x,P)%P)%P;
f[i]%=P; ans[k]+=P-L(n+m-a[i].x-a[i].y,n-a[i].x,P)*f[i]%P;
} ans[k]%=P;
} ll anss=; for(R i=;i<=tot;++i) anss+=ans[i]*M[i]%mod*T[i]%mod;
printf("%lld\n",anss%mod);

2019.05.18

最新文章

  1. ViEmu 3.6.0 过期 解除30天限制的方法
  2. [Android]使用自定义JUnit Rules、annotations和Resources进行单元测试(翻译)
  3. Java json串生成及转bean
  4. python logging模块
  5. 来自于2016.2.24的flag
  6. JVM复习笔记
  7. myBatis出现Mapped Statements collection already contains value for
  8. Android编译系统详解(一)
  9. Linux rm命令
  10. JavaScript高级程序设计(七):JavaScript中的in关键字
  11. objective-c中点语法的使用
  12. android -- 蓝牙 bluetooth (三)搜索蓝牙
  13. thinkphp学习笔记3—项目编译和调试模式
  14. hdu_5769_Substring(后缀数组)
  15. MongoDB入门系列(三):查询(SELECT)
  16. Spring-mvc设置@RequestMapping标签更改返回头及@RequestMapping简述
  17. S3C6410板子移植 Android2.2
  18. Activiti6-TaskService(学习笔记)重要
  19. 17. Debuggers (调试器 5个)
  20. Web前端JQuery面试题(三)

热门文章

  1. uoj problem 14 DZY Loves Graph
  2. Android的缓存图片不在系统图库中显示的解决办法
  3. zabbix发送邮件
  4. Scala总结
  5. 三 akka学习 actor的例子
  6. cadence spb 16.5 破解过程实例和使用感受_赤松子耶_新浪博客
  7. service使用handler与Activity沟通的两种方法
  8. Servlet编程实例 续4
  9. javascript的DI
  10. Learning Python 007 基本语句