免费建站系统对比,郑州做网站优化最好的公司,嘉定网站制作,建设网站的特色题目链接#xff1a;http://acm.split.hdu.edu.cn/showproblem.php?pid5794 题意#xff1a;让一个棋子从#xff08;1,1#xff09;走到#xff08;n#xff0c;m#xff09;#xff0c;要求像马一样走日字型并只能往右下角走。里面还有r个障碍点不能经过或者到达http://acm.split.hdu.edu.cn/showproblem.php?pid5794 题意让一个棋子从1,1走到nm要求像马一样走日字型并只能往右下角走。里面还有r个障碍点不能经过或者到达问有多少种走法可以走到nm。 思路画个图可以发现走的点像一个斜着的杨辉三角。所以可以得到一个从点 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 坐标xyxy/3就是步数了。当前的位置是minxy-步数。这里的步数就相当于三角的层数。 首先对全部障碍从小到大进行排序对于每个障碍 i求出从11走到其的路径总数减去之前的障碍0 j i可以走到现在的障碍的路径总数dp[i] - dp[j] * 从点 j 走到点 i 的路径数。组合数的计算要用到Lucas定理进行计算。 1 #include cstdio2 #include cstring3 #include algorithm4 #include string5 #include cmath6 #include iostream7 #include stack8 using namespace std;9 #define MOD 11011910 typedef long long LL;11 struct node12 {13 LL x, y;14 }p[115];15 LL dp[115];16 LL f[MOD10];17 /*18 dp[i]一开始表示从(0, 0)走到第i个点的路径数19 后面要减去如果前面有障碍,那么会有一部分路径是不能走的20 减去的路径数为分别为第j个点(0ji)走到第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 } 转载于:https://www.cnblogs.com/fightfordream/p/5827815.html
