1 条题解
-
0
C++ :
#include <cstdio> #include <cstring> #define D 64 /* 高精度位数上限(a[0] 为最低位) */ typedef struct { int a[D]; } Big; static Big f[64][64]; static void bset0(Big *r){ memset(r->a, 0, sizeof(r->a)); } static void bset1(Big *r){ bset0(r); r->a[0] = 1; } static void badd(Big *r, const Big *x){ int c = 0; for(int i = 0; i < D; i++){ int s = r->a[i] + x->a[i] + c; r->a[i] = s % 10; c = s / 10; } } static void bprint(const Big *x){ int i = D - 1; while(i > 0 && x->a[i] == 0) i--; for(; i >= 0; i--) putchar('0' + x->a[i]); putchar('\n'); } /* 马走日字且只能向右:把「向右」记作 x 增大。马在 (x,y) 处可走的 4 步为 (dx,dy) = (1,2),(2,1),(2,-1),(1,-2)(dx>0 保证向右)。 f[x][y] = Σ f[x-dx][y-dy];dx>0,故按 x 从小到大递推即可。 若 x2 < x1 或不可达,答案为 0。样例 30 30 1 15 5 15 -> 8 */ int main(){ int m, n, x1, y1, x2, y2; if(scanf("%d %d %d %d %d %d", &m, &n, &x1, &y1, &x2, &y2) != 6) return 0; for(int i = 0; i <= m + 1; i++) for(int j = 0; j <= n + 1; j++) bset0(&f[i][j]); bset1(&f[x1][y1]); int dx4[4] = {1, 2, 2, 1}; int dy4[4] = {2, 1, -1, -2}; for(int x = 1; x <= m; x++){ for(int y = 1; y <= n; y++){ if(x == x1 && y == y1) continue; bset0(&f[x][y]); for(int k = 0; k < 4; k++){ int px = x - dx4[k], py = y - dy4[k]; if(px >= 1 && px <= m && py >= 1 && py <= n) badd(&f[x][y], &f[px][py]); } } } bprint(&f[x2][y2]); return 0; }
- 1
信息
- ID
- 2674
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者