题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5794
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<ll,ll>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int maxn =2e5+5;
const int mod=110119;
const int inv2=499122177;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}/*
题目大意：给定一个二维地图的维度，
地图上有若干个陷阱，陷阱是不能走入的，
起点在（1，1），终点在（n，m）其只能在右上方，
走（1，2）或者（2，1）这样的方格步进，
问从起点到终点的方案数是多少。题目分析：对于从起点到终点（不管障碍物），方案数列个方程就好了，
假设进行了x次（1，2），y次（2，1）,那么可以解出来x和y的具体表达，
组合数就是C(x+y,y)。
再考虑障碍物，用DP的思想去删除其障碍点的影响，
由于障碍点的数量十分少，二重循环即可，
对于第i个障碍点，其初始贡献是从起点到这里的数量，
对于满足大小关系的i和j障碍点，i要减去从i到j的组合数*dp[j]。
这是为了给以后要同时用到i和j的点消去重复度。
比如既然从j可以走到i，那么i到目标点的方案其因子dp[i]就不能包含经过j的方案，
这种情况会在计算j的时候考虑进去。求组合数的时候用lucas定理搞下即可。
时间复杂度：O(m*m+110119....)*/int ca=0;
ll n,m,r,x,y;
pair<ll,ll> pp[105];
ll fac[mod+5],inv[mod+5],dp[105];
void init(){fac[0]=1LL;rep(i,1,mod) fac[i]=fac[i-1]*i%mod;inv[mod-1]=powmod(fac[mod-1],mod-2);for(int i=mod-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll p,ll q){///求组合数if(q>p||p<0||q<0)return 0LL;if(q==0||p==q) return 1LL;return fac[p]*inv[q]%mod*inv[p-q]%mod;
}
///n,m较大时需要用到lucas定理
ll lucas(ll p,ll q){if(2*q<p||2*p<q) return 0LL;ll tx=p,ty=q;if( (2*q-p)%3 || (2*p-q)%3 ) return 0LL;p=(2*ty-tx)/3,q=(2*tx-ty)/3;p+=q;ll ans=1;while(p&&q){ll a=p%mod,b=q%mod;if(a<b) return 0LL;ans=ans*C(a,b)%mod;p/=mod;q/=mod;}return ans;
}int flag;
int main(){init();///初始化while(scanf("%lld%lld%lld",&n,&m,&r)!=EOF){n--,m--,flag=0;rep(i,0,r){scanf("%lld%lld",&x,&y);x--,y--;pp[i]=make_pair(x,y);if(x==n&&y==m) flag=1;}pp[r++]=make_pair(n,m);sort(pp,pp+r);///排序mst(dp,0);///DP过程rep(i,0,r) dp[i]=lucas(pp[i].fi,pp[i].se);rep(i,0,r) rep(j,0,i) if(pp[i].fi>pp[j].fi&&pp[i].se>pp[j].se)dp[i]=(dp[i]-dp[j]*lucas( pp[i].fi-pp[j].fi , pp[i].se-pp[j].se )%mod+mod)%mod;printf("Case #%d: ",++ca);if(flag) puts("0");///以防终点就是obstracleelse printf("%lld\n",dp[r-1]);}return 0;
}