[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. 容斥:

Sort Q, the subset of mapped forbidden points
totalWays = ways(0, dest)
for each subset S of Q
    cWays = 1
    visit points in S using i = 2 to S.size, in order of appearance in Q
        cWays *= ways(S[i] - S[i-1])
    sign = (S.size % 2 == 1) ? -1 : 1
    totalWays += sign * cWays


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


方法2. 高斯消元:

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

到达终点且途径P中至少一个点的方案数=
for i = 1 to Q.size, ways += x(i) * ways(i, dest)


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


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

现在,

ways(0,j)=
for i = 1 to Qc, ways += x(i) * ways(i, j)

对所有同样在Q中的j。


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

ways(0, 1) = x(1)*ways(1, 1) + x(2)*ways(2, 1) ... + x(Qc)*ways(Qc, 1)
ways(0, 2) = x(1)*ways(1, 2) + x(2)*ways(2, 2) ... + x(Qc)*ways(Qc, 2)
ways(0, 3) = x(1)*ways(1, 3) + x(2)*ways(2, 3) ... + x(Qc)*ways(Qc, 3)
...
ways(0, Qc) = x(1)*ways(1, Qc) + x(2)*ways(2, Qc) ... + x(Qc)*ways(Qc, Qc)


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


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

方法3. 排序:

现在我们知道Q中的点是有序的。故,
Sort Q
x(1) = ways(0, 1)
for i = 2 to Q.size
    x(i) = ways(0, i)
    for j = 1 to i-1
        x(i) -= x(j) * ways(j, i)


这样在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的余数以及乘法逆元来解决。由于组合数的范围不很大,我们可以这么做:

inv = Array[10000]
for i = 2 to 10000
    inv[i] = modulo_power(i, 1000000005)
fact = Array[10000]
ifact = Array[10000]
fact[1] = ifact[1] = 1
for i = 2 to 10000
    fact[i] = fact[i-1] * i mod 1000000007
    ifact[i] = ifact[i-1] * inv[i] mod 1000000007


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


现在,

C(n,r) = fact[n]*ifact[r]*ifact[n-r] mod 1000000007


SETTERS SOLUTION

点击此处

TESTERS SOLUTION


点击此处

发表评论

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