題目鏈接：

A Simple Chess

Time Limit: 2000/1000 MS (Java/Others)???

?Memory Limit: 65536/65536 K (Java/Others)

Problem Description There is a?n×m?board, a chess want to go to the position?
(n,m)?from the position?(1,1).
The chess is able to go to position?(x2,y2)?from the position?(x1,y1), only and if only?x1,y1,x2,y2?is satisfied that?(x2?x1)2+(y2?y1)2=5,?x2>x1,?y2>y1.
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.

?

Input The input consists of multiple test cases.
For each test case:
The first line is three integers,?n,m,r,(1≤n,m≤1018,0≤r≤100), denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
Then follow?r?lines, each lines have two integers,?x,y(1≤x≤n,1≤y≤m), denoting the position of the obstacles. please note there aren't never a obstacles at position?(1,1).

?

Output For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module?110119.

?

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 題意： 走日字從(1,1)到(n,m)且不經過障礙的方案數(shù); 思路： 原來向下和向右移動的方案數(shù)是C(n+m,m),這個是先把日字變成原來熟悉的走法,可以畫個圖研究一下，最后發(fā)現(xiàn)是(0,0)到(2*fy-fx/3,2*fx-fy/3)的方案數(shù) 不經過障礙可以用容斥加dp解決,dp[i]表示從起點到達第i個點中間不經過障礙點的方案數(shù),那么dp[i]=起點到達i的總方案數(shù)-∑dp[j]*(j點到達i點的總方案數(shù)) 還有就是要預處理出階乘,同時n和m都太大要用lucas定理化簡,C(n,m)%mod=C(n/mod,m/mod)*C(n%mod,m%mod)%mod; AC代碼： #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL mod=110119; const int maxn=110; LL n,m,x[maxn],y[maxn],dp[maxn],p[110130]; int r; inline void init() {p[0]=1;for(int i=1;i<=110119;i++)p[i]=p[i-1]*(LL)i%mod; } LL pow_mod(LL a,LL b) {LL s=1,base=a;while(b){if(b&1)s=s*base%mod;base=base*base%mod;b>>=1;}return s; } LL cal(LL a,LL b) {if(a<mod&&b<mod){if(b>a)return 0;return p[a]*pow_mod(p[b],mod-2)%mod*pow_mod(p[a-b],mod-2)%mod;}return cal(a/mod,b/mod)*cal(a%mod,b%mod)%mod; } LL solve(int L,int R) {LL fx=x[R]-x[L],fy=y[R]-y[L];if((2*fy-fx)%3||(2*fx-fy)%3||2*fy<fx||2*fx<fy)return 0;LL up=(2*fy-fx)/3,down=(fx+fy)/3;return cal(down,up); } int main() {init();int Case=0;while(scanf("%lld%lld%d",&n,&m,&r)!=EOF){memset(dp,0,sizeof(dp));int flag=0;x[0]=1,y[0]=1;for(int i=1;i<=r;i++){scanf("%lld%lld",&x[i],&y[i]);if(x[i]==n&&y[i]==m)flag=1;}LL ans=0;if(!flag){x[0]=1,y[0]=1;dp[0]=1;x[++r]=n,y[r]=m;for(int i=1;i<=r;i++){for(int j=1;j<=i;j++){if(x[j]>=x[i]&&y[j]>=y[i])swap(x[i],x[j]),swap(y[i],y[j]);}}for(int i=1;i<=r;i++)dp[i]=solve(0,i);for(int i=1;i<=r;i++){for(int j=1;j<i;j++){if(x[j]<=x[i]&&y[j]<=y[i])dp[i]=(dp[i]-dp[j]*solve(j,i)%mod+mod)%mod;}}for(int i=1;i<=r;i++)if(x[i]==n&&y[i]==m)ans=dp[i];}printf("Case #%d: %lld\n",++Case,ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/zhangchengc919/p/6286327.html

總結

以上是生活随笔為你收集整理的hdu-5794 A Simple Chess(容斥+lucas+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。