[CodeChef September Challenge 2012]Knight Moving(KNGHTMOV)题解翻译

首先,让我们忘掉答案可能会非常大,需要模10^9+7这一事实。我们将稍后考虑这一问题,讨论这将对解答造成何种影响。

问题分为两种情况。

情况1:A和B线性无关

由于A和B线性无关,我们可以对空间中的所有点,向由正交向量A和B确定的空间中做一线性映射。
这意味着我们可以将每个点(u,v)用(p,q)代替,使得:

p*Ay + q*Bx = u
p*Ay + q*By = v

如果终点(X,Y)无法转换成整点(x’,y’),那么即使不考虑障碍,合法的方案数也是0。
如果某个障碍点无法转换成整点(p,q),那么该障碍点永不可能到达,可以直接忽略。

现在,我们得到了障碍点集的一个子集,不妨称之为Q。在前往终点(x’,y’)的路径上必须避开。但现在,A和B被换成了(0,1)和(1,0)。

当每步可走(1,0)或(0,1)时,从(0,0)到达(p,q)的方法就是:

ways(p,q)=C(p+q,p)

对于障碍点集Q,可以用几种方法解决。

方法1. 容斥:


时间复杂度:O(K*2^K)

方法2. 高斯消元:

到达终点而不经过Q的方案数 = 到达终点的总方案数 – 到达终点且途径Q中至少一个点的方案数。

到达终点且途径P中至少一个点的方案数=

其中x(i)是到达Q中第i个点,而不途径Q中别的点的方案数。

令Qc为Q包含的元素个数。

现在,

ways(0,j)=
对所有同样在Q中的j。

如此,我们就有了关于Qc个变量的Qc个方程:


我们可以用高斯消元法在O(N^3)的时间内解出所有的x。

一旦算出了x,我们就可以计算到达(x’,y’)且途径Q中至少一个点的方案数,自然也可以计算到达(x’,y’)而不途径Q中任何点的方案数。

方法3. 排序:

现在我们知道Q中的点是有序的。故,

这样在O(N^2)的时间内,就可以算出上述的x。

如此一来,整个问题就解决了。

情况2:A和B线性相关

有众多的特殊情况需要仔细考虑:


①A=(0,0)且B=(0,0),那么(X,Y)=(0,0)时答案为-1,否则为0。
②如果Ax和Bx都是0但X非零,答案为0.
③如果Ay和By都是0但Y非零,答案为0.

令Gx为Ax和Bx的最大公约数,Gy为Ay和By的最大公约数。

④如果X不能被Gx整除,或Y不能被Gy整除,则答案为0.

我们可以忽略掉所有符合上述条件,因而无法到达的障碍点。

现在,我们可以将X坐标缩小Gx倍,将Y坐标缩小Gy倍。当然,我们只讨论那些可以到达的点。

由于A和B线性相关,我们知道两个坐标上的情况是相似的。因此,我们可以只在X坐标上进行DP,计算到达X的方案数,我们知道这也同样会到达Y。

我们可以用Bellman-Ford算法加上动态规划来计算到达终点的方案数——最初是(x’,y’)。我们可以做两次Bellman-Ford来判断是否有环。

如果有环,将有无穷多种方案。否则DP将得到方案数。

对这种情况更详细的说明,请看tester’s solution

还有数论

在解决过程中,我们始终需要计算组合数模10^9+7的值。

而且,我们需要在模10^9+7的域内进行高斯消元,这意味着高斯消元中所有的除法都由乘以逆元的方法进行。

组合数的问题可以用预先计算阶乘模10^9+7的余数以及乘法逆元来解决。由于组合数的范围不很大,我们可以这么做:


其中fact是阶乘模10^9+7的余数,而ifact是其乘法逆元。


现在,


SETTERS SOLUTION

点击此处

TESTERS SOLUTION


点击此处

发表评论

电子邮件地址不会被公开。 必填项已用*标注