題意：一匹”馬”在棋盤上( 1 ,1)的位置,每次跳躍時橫縱坐标都必須增大.棋盤上還有 K 個障礙物(保證不在(1, 1 )處).求跳到(n, m )的方案數,對素數P= 110119 取模.
解題思路： 存障礙點的時候要進行篩選，從( 0 ,0)點到( n ,m)不經過的障礙點不存入，之後對點進行按照 x ，y進行，進行了這個預處理之後後面的dp就很簡單了。主要是結合lucas定理，當lucas中傳入的值 0時注意輸出0，這點不要忘記處理，不然會RE。代碼中注釋的非常清楚，不懂得可以看一下每一步的實作，想着挺麻煩的，其實實作起來還挺簡單的細心一點把細節處理好就行。
AC代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define mod 110119
ll n,m,r,ca,cnt,a,b,rig,up;
ll factorial[];
ll mod_pow(ll a,ll n,ll p)
{
ll ret=,A=a;
for(; n ; A=(A*A)%p,n>>=) if(n & )ret=(ret*A)%p;
return ret;
}
void init_factorial(ll p)
{
factorial[] = ;
for(ll i = ;i <= p;i++)factorial[i] = factorial[i-]*i%p;
}
ll C(ll a,ll k,ll p) //求C(n,m)%p p最大為10^5。a,b可以很大！ a個數中挑k個的組合數
{
ll re = ;
for(; a && k ; a /= p , k /= p){
ll aa = a%p;ll bb = k%p;
if(aa < bb) return ; //這個是最後的改動！
re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-,p)%p;//這兒的求逆不可先處理
}
return re;
}
ll Lucas(ll a,ll k ,ll p){
if(a< || k< || a<k)return ;
else return C(a,k,p);
}
///以上為lucas算法，将輸入為if(a<0 || k<0 || a<k)return 0;
///時直接輸出0,當是就是沒加這個判斷條件，然後就一直RE
struct Point
{
ll x,y;
bool operator < (const Point & a) const
{
if(x==a.x) return y<a.y;
return x<a.x;
}
}rock[];///重載小于号，直接sort預處理減少循環
ll dp[];///dp[]中存的是第i個位，不經過i之前的阻礙點能到達等到達i點的路徑個數。
int main()
{
// freopen("1002.in","r",stdin);
// freopen("data.out","w",stdout);
init_factorial(mod);
ca=;
ll x,y;
while(~scanf("%I64d%I64d%I64d",&n,&m,&r))
{
n--;///題目中坐标從1開始，代碼中從0開始，友善取模
m--;
cnt=;///cnt存儲符合條件的點，從1開始
for(ll i=;i<r;i++)
{
scanf("%I64d%I64d",&x,&y);
x--;
y--;
ll tx=x;
ll ty=y;
a=*y-x;
b=*x-y;
if(a%==&&b%==&&a/>=&&b/>=&&x>=&&x<=n&&y>=&&y<=m)///這層的判斷，去除不能從(0,0)到達目前點的點
{
y=m-y;
x=n-x;
a=*y-x;
b=*x-y;
if(a%==&&b%==&&a/>=&&b/>=&&x>=&&x<=n&&y>=&&y<=m)///這層判斷去除從目前點不能到達(n,m)的點
{
rock[++cnt].x=tx;
rock[cnt].y=ty;
}
}
}
sort(rock+,rock+cnt+);///經過篩選之後，rock中所有的點都能到達，并且到達(n,m)點
if((*m-n)%!=||(*n-m)%!=||(*m-n)/<||(*n-m)/<)///當從(0,0)點不能到達(n,m)點直接輸出0
{
printf("Case #%I64d: %I64d\n",ca++,(ll));
continue;
}
rock[++cnt].x=n;///将(n,m)點存入rock中，這樣dp[cnt]直接是答案了
rock[cnt].y=m;
for(ll i=;i<=cnt;i++)
{
a=(*rock[i].y-rock[i].x)/;
b=(*rock[i].x-rock[i].y)/;
dp[i]=Lucas(a+b,a,mod);先将地i個點的路徑記錄下來，
for(ll j=;j<i;j++)
{
ll ta=rock[i].x-rock[j].x;
ll tb=rock[i].y-rock[j].y;
ll taa=(*ta-tb)/;
ll tbb=(*tb-ta)/;
if(rock[i].x>=rock[j].x&&rock[i].y>=rock[j].y)
dp[i]=((dp[i]-dp[j]*Lucas(taa+tbb,taa,mod))%mod+mod)%mod;///減去經過之前的點的路徑個數
}
}
printf("Case #%I64d: %I64d\n",ca++,dp[cnt]);
}
return ;
}