题目描述
棋子在(n*m)棋盘上可以走马步（横走(1)竖走(2)或横走(2)竖走(1)）
只能往格子坐标增大的方向跳，且棋盘中会有一些障碍物
问棋子从(（1,1）)走到(（n,m）)有几种方案mod((110119))
Input
输入包含多组数据
第一行三个整数(n,m,r,(1<=n,m<=1e18,0<=r<=100),)
接下来(r)行，每行两个整数(x,y,(1<=x<=n,1<=y<=m),)
表示障碍物位置((1,1))上不会有障碍物
Output
对于每组测试数据，输出一行"Case #x: y"，x是组数,y是答案
Sample Input
1 1 0
3 3 0
4 4 1
2 1
4 4 1
3 2
7 10 2
1 2
7 1
Sample Output
Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 5
容斥(dp)+(lucas)定理。
题目要我们求出不碰到任意障碍物的方案数，直接求这个方案数是十分麻烦的。
我们可以转换成从起点出发到第(i)个障碍物不碰到任意障碍物的方案数。
我们先把在((n,m))处放置一个障碍物，再把所有的障碍物按照(x)排序。
我们定义(dp[i])表示从起点出发到第(i)个障碍物不碰到任意障碍物的方案数。
(calc[x1,y1,x2,y2])表示从(x1,y1)到第(x2,y2)个障碍物的方案数。
排序好之后，我们对于第(i)个障碍物:
(dp[i]=calc[1,1,x_i,y_i]-sum calc(x_j,y_j,x_i,y_i)*dp[j]，（j=起点到第i的路径上的障碍）)。
现在我们就是要求出(calc(x1,y1,x2,y2))。
首先设(X=x2-x1，Y=y2-y1)，横走(1)竖走(2)走了(a)步，或横走(2)竖走(1)走了(b)步。
所以我们有(a+2*b=X)和(b+2*a=Y)。
我们可以解出(a,b)，若(a,b)无整数解则无法从((x1,y1))到((x2,y2))。
解出了(a,b)后答案就是(C(a+b,a))了。
只是(a,b)比较大，而我们发现模数(110119)是一个质数。
所以我们可以利用(lucas)定理。
(lucas)定理：当(p)为质数时，(C(a,b)\%p=C(a/p,b/p)*C(a\%p,b\%p)\%p)。
代码如下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
#define reg register
#define Raed Read
#define clr(a,b) memset(a,b,sizeof a)
#define Mod(x) (x>=mod)&&(x-=mod)
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>(b)?(b):(a))
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
#pragma GCC target("avx,avx2,sse4.2")
#pragma GCC optimize(3)
inline int Read(void) {
int res=0,f=1;
char c;
while(c=getchar(),c<48||c>57)if(c=='-')f=0;
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>=48&&c<=57);
return f?res:-res;
}
template<class T>inline bool Min(T &a, T const&b) {
return a>b?a=b,1:0;
}
template<class T>inline bool Max(T &a, T const&b) {
return a<b?a=b,1:0;
}
const int N=105,M=1e5+5,mod=110119;
bool MOP1;
struct node {
int x,y;
bool operator<(node _)const {
if(x==_.x)return y<_.y;
return x<_.x;
}
} A[N];
int dp[N];
bool MOP2;
int Fac[mod+5],Inv[mod+5],V[mod+5];
int C(int a,int b) {
if(a<b||b<0)return 0;
if(a<mod&&b<mod)return 1ll*Fac[a]*((1ll*Inv[a-b]*Inv[b])%mod)%mod;
return (1ll*C(a%mod,b%mod)*C(a/mod,b/mod)%mod)%mod;
}
inline int calc(int x,int y) {
int tot=x+y;
if(tot%3)return 0;
int a=x-tot/3,b=y-tot/3;
return C(a+b,a);
}
inline void _main(void) {
int Case=0,n,m,k;
Fac[0]=Inv[0]=Fac[1]=V[1]=Inv[1]=1ll;
ret(i,2,mod) {
Fac[i]=(1ll*Fac[i-1]*i)%mod;
V[i]=1ll*(mod-mod/i)*V[mod%i]%mod;
Inv[i]=(1ll*Inv[i-1]*V[i])%mod;
}
while(~scanf("%lld %lld %lld",&n,&m,&k)) {
int f=0;
rep(i,1,k) {
A[i]=(node)<%Read(),Read()%>;
if(A[i].x==n&&A[i].y==m)f=1;
}
A[++k]=(node)<%n,m%>,sort(A+1,A+k+1);
clr(dp,0);
rep(i,1,k) {
dp[i]=calc(A[i].x-1,A[i].y-1);
ret(j,1,i)if(A[j].y<=A[i].y) {
int res=(dp[j]*calc(A[i].x-A[j].x,A[i].y-A[j].y))%mod;
dp[i]=((dp[i]-res)%mod+mod)%mod;
}
}
printf("Case #%lld: %lld
",++Case,dp[k]);
}
}
signed main() {
_main();
return 0;
}