HDU 5794 - A Simple Chess
题意：马(象棋)初始位置在(1,1), 现在要走到(n,m), 问有几种走法
棋盘上有r个障碍物, 该位置不能走, 并规定只能走右下方
数据范围： ( 1 ≤ n,m ≤10^18, 0 ≤ r ≤100 )
分析：分析不存在障碍物时的走法规律：
(1,1) 1 (2,3) (3,2) 1 1 (3,5) (4,4) (5,3) 1 2 1 (4,7) (5,6) (6,5) (7,4) 1 3 3 1 ...... ...... 发现走法规律是一个斜着的杨辉三角, 即i层第j个的走法数为： C[i,j-1] (组合数)
那么根据换算, 层数 = (x+y+1)/3 - 1 , 个数 = x - (x+y+1)/3
即可得到无障碍物时，(m,n)点的路径数
分析障碍物的贡献与障碍物之间的相互影响：障碍物(x,y)的贡献 = (1,1)到(x,y)的路径数 * (x,y)到(n,m)的路径数, 后者通过相对位置(平移)计算
障碍物之间的影响, 即应去掉的重复部分, 也如此计算
因为n，m数据范围大， 故计算组合数应用 LUCAS定理
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define LL long long 7 const LL MOD = 110119; 8 long long fac[MOD]; 9 //求a^n % MOD的值 10 template 11 T1 QuickPow(T1 x, T2 n, T1 MOD) 12 { 13 T1 ans = 1; 14 while (n) 15 { 16 if (n & 1) ans = (ans * x) % MOD; 17 x = (x * x) % MOD; 18 n >>= 1; 19 } 20 return ans; 21 } 22 //组合数 23 //参数为C(n, m) % p (p为质数) 24 //fac[i]表示i! % p 25 template 26 T C(Type n, Type m, T p) 27 { 28 if (n < m) return 0; 29 T x = fac[n], y = fac[n-m] * fac[m] % p; 30 return x * QuickPow(y, p - 2, p) % p; 31 } 32 //生成i! % p (i = 0->p-1) 33 //配合Lucas定理使用 34 template 35 void ProFac(T *fac, T p) 36 { 37 fac[0] = 1; 38 for (int i = 1; i < (int)p; i++) 39 fac[i] = fac[i-1] * i % p; 40 } 41 //Lucas定理 42 //求C(n, m) % p (n, m可以很大, p最大可为1e5, p为质数) 43 //后面两个参数内部使用，不必考虑 44 template 45 T Lucas(T n, T m, T p) 46 { 47 if (m == 0) return 1LL; 48 else 49 { 50 T res = C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p; 51 return res; 52 } 53 } 54 55 56 inline bool change(LL x,LL y, LL &m,LL &n) //将(x,y) 转为 C[b][a] 57 { 58 if((x + y + 1) % 3 != 0 ) return 0; 59 LL a = (x + y + 1) / 3; 60 if(x < a || y < a) return 0; 61 m = x - a; 62 n = a - 1; 63 return 1; 64 } 65 66 struct CC 67 { 68 LL x, y, a, b; 69 }g[105]; 70 LL n, m, a, b; 71 int r, tot; 72 LL gx[105], gy[105], val[105]; 73 LL ans; 74 75 bool cmp(CC a, CC b) 76 { 77 return a.b < b.b; 78 } 79 bool flag; 80 int main() 81 { 82 ProFac(fac, MOD); 83 int tt = 1; 84 while (~scanf("%lld%lld%d",&n,&m,&r)) 85 { 86 flag = 0; 87 for (int i = 1; i <= r; i++) 88 { 89 scanf("%lld%lld", &gx[i], &gy[i]); 90 if(gx[i] == n && gy[i] == m) flag = 1; 91 } 92 printf("Case #%d: ", tt++); 93 if (flag || !change(n, m, a, b)) //障碍物在 n,m 点,或者不能跳到n,m 94 { 95 puts("0"); continue; 96 } 97 tot = 0; 98 for (int i = 1; i <= r; i++) 99 {100 if (!change(n - gx[i] + 1,m - gy[i] + 1, g[tot].a, g[tot].b)) continue; //该位置不能影响到 n,m点 101 if (change(gx[i], gy[i], g[tot].a, g[tot].b)) // 有效障碍物点102 {103 g[tot].x = gx[i], g[tot].y = gy[i];104 tot++;105 }106 }107 ans = Lucas(b, a, MOD);//C[b][a]108 sort(g, g + tot, cmp);109 for (int i = 0; i < tot; i++)110 {111 val[i] = Lucas(g[i].b, g[i].a, MOD);//到每个障碍物的的路径数 112 }113 for (int i = 0; i < tot; i++)114 {115 LL a1, b1, tmp;116 if (!change(n - g[i].x + 1, m - g[i].y + 1, a1, b1) ) continue;117 tmp = Lucas(b1, a1, MOD);118 ans = (ans + MOD - (val[i] * tmp % MOD )) % MOD;//减去障碍物贡献 119 for (int j = i + 1; j < tot; j++)120 {121 if ( !change(g[j].x - g[i].x + 1, g[j].y - g[i].y + 1, a1, b1) ) continue;122 tmp = Lucas(b1, a1, MOD);123 val[j] = (val[j] + MOD - (val[i] * tmp % MOD )) % MOD; //减去障碍物之间的影响 124 }125 }126 printf("%lld\n", ans);127 }128 }