首页 > 代码库 > HDU 5794：A Simple Chess（Lucas + DP）
HDU 5794：A Simple Chess（Lucas + DP）
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5794
题意：让一个棋子从（1,1）走到（n，m），要求像马一样走日字型并只能往右下角走。里面还有r个障碍点不能经过或者到达，问有多少种走法可以走到（n，m）。
思路：画个图可以发现走的点像一个斜着的杨辉三角。所以可以得到一个从点 i 走到点 j 的路径数是一个组合数。
大概就是长这样，杨辉三角的每个点的数如下。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
找到规律：路径数为C（在这一步的位置，走过的步数）。走过的步数是当前的点 i 坐标（x，y），（x+y）/3就是步数了。当前的位置是min（x，y）-步数。这里的步数就相当于三角的层数。
首先对全部障碍从小到大进行排序，对于每个障碍 i，求出从（1，1）走到其的路径总数，减去之前的障碍（0 <= j < i）可以走到现在的障碍的路径总数（dp[i] -= dp[j] * 从点 j 走到点 i 的路径数）。组合数的计算要用到Lucas定理进行计算。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <string> 5 #include <cmath> 6 #include <iostream> 7 #include <stack> 8 using namespace std; 9 #define MOD 110119 10 typedef long long LL; 11 struct node 12 { 13 LL x, y; 14 }p[115]; 15 LL dp[115]; 16 LL f[MOD+10]; 17 /* 18 dp[i]一开始表示从(0, 0)走到第i个点的路径数 19 后面要减去如果前面有障碍,那么会有一部分路径是不能走的 20 减去的路径数为分别为第j个点(0<=j<i)走到第i个点的路径数*dp[j] 21 */ 22 23 bool cmp(const node &a, const node &b) 24 { 25 if(a.x == b.x) return a.y < b.y; 26 return a.x < b.x; 27 } 28 29 void biao() //打出阶乘表 30 { 31 f[0] = f[1] = 1; 32 for(int i = 2; i <= MOD; i++) { 33 f[i] = f[i-1] * i % MOD; 34 } 35 } 36 37 LL quick_pow(LL a, LL b) 38 { 39 a %= MOD, b %= MOD; 40 LL ans = 1; 41 while(b) { 42 if(b & 1) ans = ans * a % MOD; 43 a = a * a % MOD; 44 b >>= 1; 45 } 46 return ans; 47 } 48 49 LL C(LL n, LL m) 50 { 51 if(m > n) return 0; 52 if(m < 0) return 0; 53 LL ans = 1; 54 ans = ans * f[n] % MOD * quick_pow(f[m] * f[n-m] % MOD, MOD - 2) % MOD; 55 return ans; 56 } 57 58 LL Lucas(LL n, LL m) 59 { 60 if(m == 0) return 1; 61 return C(n % MOD, m % MOD) % MOD * Lucas(n / MOD, m / MOD) % MOD; 62 } 63 64 int main() 65 { 66 LL n, m, r; 67 int cas = 0; 68 biao(); 69 while(~scanf("%I64d%I64d%I64d", &n, &m, &r)) { 70 memset(dp, 0, sizeof(dp)); 71 bool flag = 0; 72 for(int i = 0; i < r; i++) { 73 scanf("%I64d%I64d", &p[i].x, &p[i].y); 74 if(p[i].x == n && p[i].y == m) flag = 1; 75 p[i].x--, p[i].y--; 76 } 77 sort(p, p + r, cmp); 78 p[r].x = n - 1, p[r].y = m - 1; //把目标点加入 79 printf("Case #%d: ", ++cas); 80 if(flag || (p[r].x + p[r].y) % 3 != 0) { //如果障碍在目标点上或者不能走到目标点 81 puts("0"); continue; 82 } 83 for(int i = 0; i <= r; i++) { 84 if((p[i].x + p[i].y) % 3 == 0) { //如果这个障碍是可以走到的 85 LL a = (p[i].x + p[i].y) / 3; //第几层 86 LL b = min(p[i].x, p[i].y) - a; //位置 87 dp[i] = Lucas(a, b); //类似于杨辉三角的组合数 88 for(int j = 0; j < i; j++) { 89 if(p[j].y >= p[i].y || p[j].x >= p[i].x) continue; //题目要求只能往右下角走 90 LL xx = (p[i].x - p[j].x); 91 LL yy = (p[i].y - p[j].y); 92 if((xx + yy) % 3 == 0) { //要能够从j点走到i点 93 LL aa = (xx + yy) / 3; 94 LL bb = min(xx, yy) - aa; //减去可以从j点走到i点的路径数 95 dp[i] -= (Lucas(aa, bb) * dp[j]) % MOD; 96 dp[i] = (dp[i] + MOD) % MOD; 97 } 98 } 99 }100 }101 printf("%I64d\n", dp[r]);102 }103 return 0;104 }
HDU 5794：A Simple Chess（Lucas + DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。