3782: 上学路线
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 192 Solved: 75
[Submit][Status][Discuss]
Description
小C所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。小C家住在西南角，学校在东北角。现在有T个路口进行施工，小C不能通过这些路口。小C喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小C又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小C只需要让你求出路径数mod P的值。
Input
第一行，四个整数N、M、T、P。
接下来的T行，每行两个整数，表示施工的路口的坐标。
Output
一行，一个整数，路径数mod P的值。
HINT
1<=N,M<=10^10
0<=T<=200
p=1000003或p=1019663265
终于A掉了
这道题太可怕了
跟PoPoQQQ大爷的代码拍了好几组数据才改完Bug
首先想怎么算方案数
总-不合法
用容斥原理？好麻烦
发现一个点只会对$x,y$都比它大的点产生影响
$f[i]$表示走到点$i$不碰到其他点的方案数
$f[i]={x_i+y_i\choose x_i} - \sum\limits_{x_j<=x_i\ ,\ y_j<=y_i\ ,\ j\neq i}{x_i-x_j+y_i-y_j\choose x_i-x_j}*f[j] $
剩下的就是怎么计算组合数了
1000003直接用Lucas定理
1019663265和古代猪文一样是4个质数的乘积，Lucas定理+CRT合并
说一下问题：
1.DP时要时刻记住取模、
2.小心n和m溢出int
3.组合数n<m特判在用Lucas定理的时候不能丢！因为模意义下可能发生n<m!!!
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e6+;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
ll n,m,P;
int t;
struct Point{
ll x,y;
bool operator <(const Point &a)const{
return x<a.x||(x==a.x&&y<a.y);
}
}a[];
namespace A{
ll P=;
ll inv[N],fac[N],facInv[N];
void ini(){
inv[]=fac[]=facInv[]=;
for(int i=;i<=P;i++){
if(i!=) inv[i]=-P/i*inv[P%i]%P;
inv[i]+=inv[i]<?P:;
fac[i]=fac[i-]*i%P;
facInv[i]=facInv[i-]*inv[i]%P;
}
}
ll C(int n,int m){
if(n<m) return ;
return fac[n]*facInv[m]%P*facInv[n-m];
}
ll Lucas(ll n,ll m){
if(n<m) return ;
ll re=;
for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;
return re;
}
ll f[];
void dp(){
for(int i=;i<=t;i++){
f[i]=Lucas(a[i].x+a[i].y,a[i].x);//printf("fo %d %lld\n",i,f[i]);
for(int j=;j<i;j++)
if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
f[i]=(f[i]- Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P +P)%P;
//printf("oh %d %lld %lld \n",j ,Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P ,f[i]);
//printf("f %d %lld\n",i,f[i]);
}
}
void solve(){
ini();
dp();
printf("%lld",f[t]);
}
}
namespace B{
ll P[]={,,,,};
const int N=1e5+;
ll Pow(ll a,ll b,ll P){
if(a==) return ;
ll re=;
for(;b;b>>=,a=a*a%P)
if(b&) re=re*a%P;
return re;
}
ll Inv(ll a,ll P){return Pow(a,P-,P);}
ll inv[N][],fac[N][],facInv[N][];
void ini(){
for(int j=;j<=;j++){
int MOD=P[j];
inv[][j]=fac[][j]=facInv[][j]=;
for(int i=;i<=MOD;i++){
if(i!=) inv[i][j]=-MOD/i*inv[MOD%i][j]%MOD;
if(inv[i][j]<) inv[i][j]+=MOD;
fac[i][j]=fac[i-][j]*i%MOD;
facInv[i][j]=facInv[i-][j]*inv[i][j]%MOD;
}
}
}
ll C(int n,int m,int j){//printf("C %d %d %d %lld %lld\n",n,m,j,fac[n][j],facInv[m][j]);
if(n<m) return ;
ll p=P[j];
return fac[n][j]*facInv[m][j]%p*facInv[n-m][j]%p;
}
ll lucas(ll n,ll m,int j){
if(n<m) return ;
ll MOD=P[],a=,p=P[j];
for(;m;m/=p,n/=p) a=a*C(n%p,m%p,j)%p;
return a*(MOD/p)%MOD*Inv(MOD/p,p)%MOD;
}
ll Lucas(ll n,ll m){//printf("Lucas1 %lld %lld\n",n,m);
ll re=,MOD=P[];
for(int i=;i<=;i++)
re=(re+lucas(n,m,i))%MOD;
return re;
} ll f[];
void dp(){
for(int i=;i<=t;i++){
f[i]=Lucas(a[i].x+a[i].y,a[i].x);//printf("fo %d %lld\n",i,f[i]);
for(int j=;j<i;j++)
if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
f[i]=(f[i]- Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P[] +P[])%P[];
//printf("oh %d %lld %lld \n",j ,Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j] ,f[i]);
// printf("fn %d %lld\n",i,f[i]);
}
}
void solve(){
ini();
dp();
//for(int i=1;i<=t;i++)
// printf("Point %lld %lld %lld\n",a[i].x,a[i].y,f[i]);
printf("%lld",f[t]);
}
}
int main(){
freopen("in","r",stdin);
n=read();m=read();
t=read();P=read();
for(int i=;i<=t;i++) a[i].x=read(),a[i].y=read();
a[++t].x=n;a[t].y=m;
sort(a+,a++t);
if(P==) A::solve();
else B::solve();
}