【HDU】 5794 A Simple Chess

本文主要是介绍【HDU】 5794 A Simple Chess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A Simple Chess

---

题目链接

• A Simple Chess

---

题目大意

    一个棋子从（1，1）到（n，m），要求跳日字，其中可能还有障碍，问你总共有多少种跳法。

---

题解

Lucas定理+DP（容斥）

    首先可以通过数学求得从（1，1）跳到（n，m）的步数，然后可以直接用组合数求得步数，我这里用k1,k2代表向右和向下跳的步数，那么总步数就是$C_{k_1+k_2}^{k_1}$。
    注意到有障碍，所以总步数要减去一部分走过障碍的步数，这里我们采用dp的方法

$$设dp_i：走到第i个障碍，不经过其他障碍物时的方法数 \\ \therefore dp_i=dp_j*way(i->j)$$
    中间的 $way(i->j)$代表从i到j的路径数。
    我们把终点放进数组中直接求就可以了。

---

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long
#define mod 110119using namespace std;struct node
{LL x,y;bool operator <(const node &c) const{if (x!=c.x) return x<c.x;return y<c.y;}
};
node a[105];
LL n,m,f[mod+10],d[105];
int r;void setup()
{f[0]=1;for (int i=1;i<=mod;i++) f[i]=(f[i-1]*i)%mod;
}LL pow_mod(LL a,LL b,LL c)
{LL ans=1;while (b){if (b&1) ans=(ans*a)%c;b>>=1;a=(a*a)%c;}return ans;
}LL solve(LL n,LL k,LL p)
{if (n<0||k<0) return 0;if (n<k) return 0;LL ret=1;while (n&&k){LL nn=n%p, kk =k%p;if (nn < kk) return 0;ret=ret*f[nn]*pow_mod(f[kk]*f[nn-kk] %p,p-2,p)%p;n/=p, k/=p;}return ret;
}int main()
{int Case=1;setup();while (scanf("%lld%lld%d",&n,&m,&r)!=EOF){memset(d,0,sizeof(d));memset(a,0,sizeof(a));for (int i=0;i<r;i++) scanf("%lld%lld",&a[i].x,&a[i].y);LL k1,k2;if ((n%3+m%3-2)!=0){printf("Case #%d: 0\n",Case++);continue;}sort(a,a+r);a[r].x=n; a[r].y=m;for (int i=0;i<=r;i++){if ((a[i].x-1+a[i].y-1)%3==0){k1=(2*a[i].y-a[i].x-1)/3; k2=(2*a[i].x-a[i].y-1)/3;d[i]=solve(k1+k2,k1,mod);for (int j=0;j<i;j++) if ((a[i].x-a[j].x+a[i].y-a[j].y)%3==0){k1=(2*(a[i].y-a[j].y)+a[j].x-a[i].x)/3; k2=(2*(a[i].x-a[j].x)+a[j].y-a[i].y)/3;d[i]-=d[j]*solve(k1+k2,k1,mod)%mod;d[i]=(d[i]+mod)%mod;}}}printf("Case #%d: %lld\n",Case++,d[r]);}return 0;
}

这篇关于【HDU】 5794 A Simple Chess的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---