bzoj3782&luogu4478 [BJWC2018]上学路线

bzoj3782&luogu4478 [BJWC2018]上学路线

​​ Description 小C所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。小C家住在西南角，学校在东北角。现在有T个路口进行施工，小C不能通过这些路口。小C喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小C又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小C只需要让你求出路径数mod P的值。 Input 第一行，四个整数N、M、T、P。 接下来的T行，每行两个整数，表示施工的路口的坐标。 Output 一行，一个整数，路径数mod P的值。

Sample Input 3 4 3 1019663265 3 0 1 1 2 2 Sample Output 8 HINT 1<=N,M<=10^10 0<=T<=200 p=1000003或p=1019663265 Source 模数不是质数不能直接使用lucas 考虑分解质因数 然后crt合并即可 M=m[i].. CRT: c[i](M/m[i])*inv(M/m[i],m[i])%M

#include#include#define ll long longusing namespace std;const int N=220;struct node{ ll x,y;}d[N];ll n,m;int mod,t,dp[N];inline void inc(int &x,int v){x=x+v>=mod?x+v-mod:x+v;}inline void dec(int &x,int v){x=x-v<0?x-v+mod:x-v;}inline bool cmp(const node &a,const node &b){ return a.x==b.x?a.y>=1)if (t&1) tmp=tmp*b%mod;return tmp;}namespace sol1{ int jc[1000010],inv[1000010]; inline void init(){ jc[0]=1; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。