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定理
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const LL MOD = ;
long long fac[MOD];
//求a^n % MOD的值
template<class T1, class T2>
T1 QuickPow(T1 x, T2 n, T1 MOD)
{
T1 ans = ;
while (n)
{
if (n & ) ans = (ans * x) % MOD;
x = (x * x) % MOD;
n >>= ;
}
return ans;
}
//组合数
//参数为C(n, m) % p (p为质数)
//fac[i]表示i! % p
template<class T, class Type>
T C(Type n, Type m, T p)
{
if (n < m) return ;
T x = fac[n], y = fac[n-m] * fac[m] % p;
return x * QuickPow(y, p - , p) % p;
}
//生成i! % p (i = 0->p-1)
//配合Lucas定理使用
template<class T>
void ProFac(T *fac, T p)
{
fac[] = ;
for (int i = ; i < (int)p; i++)
fac[i] = fac[i-] * i % p;
}
//Lucas定理
//求C(n, m) % p (n, m可以很大, p最大可为1e5, p为质数)
//后面两个参数内部使用，不必考虑
template<class T>
T Lucas(T n, T m, T p)
{
if (m == ) return 1LL;
else
{
T res = C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
return res;
}
} inline bool change(LL x,LL y, LL &m,LL &n) //将(x,y) 转为 C[b][a]
{
if((x + y + ) % != ) return ;
LL a = (x + y + ) / ;
if(x < a || y < a) return ;
m = x - a;
n = a - ;
return ;
} struct CC
{
LL x, y, a, b;
}g[];
LL n, m, a, b;
int r, tot;
LL gx[], gy[], val[];
LL ans; bool cmp(CC a, CC b)
{
return a.b < b.b;
}
bool flag;
int main()
{
ProFac(fac, MOD);
int tt = ;
while (~scanf("%lld%lld%d",&n,&m,&r))
{
flag = ;
for (int i = ; i <= r; i++)
{
scanf("%lld%lld", &gx[i], &gy[i]);
if(gx[i] == n && gy[i] == m) flag = ;
}
printf("Case #%d: ", tt++);
if (flag || !change(n, m, a, b)) //障碍物在 n,m 点,或者不能跳到n,m
{
puts(""); continue;
}
tot = ;
for (int i = ; i <= r; i++)
{
if (!change(n - gx[i] + ,m - gy[i] + , g[tot].a, g[tot].b)) continue; //该位置不能影响到 n,m点
if (change(gx[i], gy[i], g[tot].a, g[tot].b)) // 有效障碍物点
{
g[tot].x = gx[i], g[tot].y = gy[i];
tot++;
}
}
ans = Lucas(b, a, MOD);//C[b][a]
sort(g, g + tot, cmp);
for (int i = ; i < tot; i++)
{
val[i] = Lucas(g[i].b, g[i].a, MOD);//到每个障碍物的的路径数
}
for (int i = ; i < tot; i++)
{
LL a1, b1, tmp;
if (!change(n - g[i].x + , m - g[i].y + , a1, b1) ) continue;
tmp = Lucas(b1, a1, MOD);
ans = (ans + MOD - (val[i] * tmp % MOD )) % MOD;//减去障碍物贡献
for (int j = i + ; j < tot; j++)
{
if ( !change(g[j].x - g[i].x + , g[j].y - g[i].y + , a1, b1) ) continue;
tmp = Lucas(b1, a1, MOD);
val[j] = (val[j] + MOD - (val[i] * tmp % MOD )) % MOD; //减去障碍物之间的影响
}
}
printf("%lld\n", ans);
}
}