3

也许您会对如何解决以下问题有所了解。

约翰决定给儿子约翰尼买一些数学玩具。他最喜欢的玩具之一是不同颜色的积木。约翰决定购买不同颜色的 C 块。对于每种颜色，他都会购买 googol (10^100) 块。所有相同颜色的块具有相同的长度。但是不同颜色的块的长度可能会有所不同。Jhonny 决定使用这些块来制作一个 1 xn 的大块。他想知道有多少种方法可以做到这一点。如果存在颜色不同的位置，则认为两种方式不同。该示例显示了一个大小为 5 的红色块、大小为 3 的蓝色块和大小为 3 的绿色块。它显示了制作长度为 11 的大块的 12 种方法。

每个测试用例以整数 1 ≤ C ≤ 100 开始。下一行包含 c 个整数。第 i 个整数 1 ≤ leni ≤ 750 表示第 i 个颜色的长度。下一行是正整数 N ≤ 10^15。

对于 T <= 25 个测试用例，这个问题应该在 20 秒内解决。应该计算答案MOD 100000007（质数）。

它可以推导出为矩阵求幂问题，使用Coppersmith-Winograd算法和快速求幂可以在 O(N^2.376*log(max(leni))) 内相对有效地解决。但似乎需要更有效的算法，因为 Coppersmith-Winograd 意味着一个很大的常数因子。你还有其他建议吗？它可能是数论或分而治之的问题

4

5 回答 5

5

首先注意你拥有的每种颜色的块数是一个完整的红鲱鱼，因为 10^100 > N 总是。所以每种颜色的块数实际上是无限的。

现在请注意，在每个位置，p（如果有一个有效的配置，不留空格等）必须有一个颜色的块，c。有len[c]办法让这个块位于，所以它仍然位于这个位置上，p。

我的想法是在固定位置尝试所有可能的颜色和位置（N/2因为它将范围减半），然后对于每种情况，b在此固定颜色块之前和此固定颜色块之后都有单元格a。因此，如果我们定义一个函数，该函数ways(i)返回平铺i单元格的方法数（带有ways(0)=1）。那么在某个位置用固定色块平铺多个单元格的方法数是ways(b)*ways(a)。将所有可能的配置相加得出ways(i).

现在我选择了固定位置，N/2因为它将范围减半，并且您大多数ceil(log(N))时候可以将范围减半。现在，由于您正在移动一个块，N/2因此您必须计算 fromN/2-750到N/2-750，750块可以具有的最大长度在哪里。因此，您必须计算750*ceil(log(N))（由于方差而更多）长度才能获得最终答案。

因此，为了获得良好的性能，您必须完成记忆，因为这本质上是一种递归算法。

所以使用Python（因为我很懒，不想写一个大数字类）：

T = int(raw_input())

for case in xrange(T):
    #read in the data
    C = int(raw_input())
    lengths = map(int, raw_input().split())
    minlength = min(lengths)
    n = int(raw_input())

    #setup memoisation, note all lengths less than the minimum length are
    #set to 0 as the algorithm needs this
    memoise = {}
    memoise[0] = 1
    for length in xrange(1, minlength):
       memoise[length] = 0

    def solve(n):
        global memoise
        if n in memoise:
            return memoise[n]

        ans = 0
        for i in xrange(C):
            if lengths[i] > n:
                continue
            if lengths[i] == n:
                ans += 1
                ans %= 100000007
                continue 
            for j in xrange(0, lengths[i]):
                b = n/2-lengths[i]+j
                a = n-(n/2+j)
                if b < 0 or a < 0:
                    continue
                ans += solve(b)*solve(a)
                ans %= 100000007
        memoise[n] = ans
        return memoise[n]
    solve(n)
    print "Case %d: %d" % (case+1, memoise[n])

请注意，我没有对此进行详尽的测试，但如果您将此算法翻译成 C++ 或类似的语言，我很确定它会满足 20 秒的时间限制。

编辑：运行一个测试N = 10^15和一个长度750我得到的块，memoise其中包含大约60000元素，这意味着非查找位的solve(n)调用次数大约相同。

于 2010-10-29T23:42:23.917 回答
2

请注意：在 c=2、len1=1、len2=2 的情况下，答案将是第 N 个斐波那契数，并且斐波那契数（大约）以黄金比例的增长因子 phi 呈指数增长~ 1.61803399。对于 N=10^15 的巨大值，答案将是大约 phi^(10^15)，一个巨大的数字。答案将具有 (ln(phi^(10^15))/ln(2)) / (8 * 2^40) ~ 79 TB 的存储要求。由于您甚至无法在 20 秒内访问79 TB，因此在这种特殊情况下您不太可能满足速度要求。

当 C 不太大并且 leni 对所有 i 都很大时，你的最大希望就出现了。在这种情况下，答案仍然会随着 N 呈指数增长，但增长因子可能会小得多。

我建议您首先构造整数矩阵 M，它将根据 (i, ..., i+k-1) 项计算序列中的 (i+1,..., i+k) 项。（只有这个矩阵的第 k+1 行是有趣的）。“手动”计算前 k 个条目，然后根据重复平方技巧计算 M^(10^15)，并将其应用于项 (0...k-1)。

矩阵的（整数）条目将呈指数增长，可能太快而无法处理。如果是这种情况，请对几个中等大小的素数 p 进行相同的计算，但取模 p。这将允许您在不使用 bigint 矩阵的情况下为各种 p 获得模 p 的答案。在使用了足够多的素数以使您知道它们的乘积大于您的答案之后，您可以使用所谓的“中国剩余定理”从您的 mod-p 答案中恢复您的答案。

于 2010-10-31T16:32:25.413 回答
2

我想在早期的@JPvdMerwe 解决方案的基础上进行一些改进。在他的回答中，@JPvdMerwe 使用了动态编程/记忆方法，我同意这是解决这个问题的方法。将问题递归地划分为两个较小的问题并记住先前计算的结果是非常有效的。

我想提出一些可以进一步加快速度的改进：

  1. 无需遍历所有可以定位中间块的方式，您只需遍历前半部分，然后将解乘以 2。这是因为后半部分的情况是对称的。对于奇数长度的块，您仍然需要将居中位置作为单独的情况。

  2. 一般来说，迭代实现可以比递归实现快几个数量级。这是因为递归实现会为每个函数调用带来记账开销。将解决方案转换为其迭代表亲可能是一个挑战，但通常是可能的。@JPvdMerwe 解决方案可以通过使用堆栈来存储中间值来进行迭代。

  3. 模运算很昂贵，在较小程度上的乘法也是如此。通过将颜色环与位置环切换，乘法和模数的数量可以减少大约 C=100 倍。这允许您在进行乘法和取模之前将多个调用的返回值添加到solve()。

测试解决方案性能的一个好方法是使用病态案例。以下内容可能特别令人生畏：长度 10^15，C=100，主要块大小。

希望这可以帮助。

于 2010-11-04T00:29:17.850 回答
0

在上面的答案中

    ans += 1
    ans %= 100000007

没有一般模数可能会快得多：

    ans += 1
    if ans == 100000007 then ans = 0
于 2010-11-05T05:56:06.873 回答
0

Please see TopCoder thread for a solution. No one was close enough to find the answer in this thread.

于 2010-11-07T11:16:24.080 回答