编程问题 - 积木游戏

Question

也许您会知道如何解决以下问题。

约翰决定给他的儿子约翰尼买一些数学玩具。他最喜欢的玩具之一是不同颜色的积木。约翰决定购买 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 算法和快速求幂。但似乎需要更有效的算法，因为 Coppersmith-Winograd 意味着一个很大的常数因子。您还有其他想法吗？这可能是一个数论或分治问题

Answer 1

首先注意你所拥有的每种颜色的块数是一个完整的红鲱鱼，因为 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 的块，因此您必须从 N/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])

注意我还没有详尽地测试这个，但我很确定它会满足20秒的时间限制，如果你翻译这个算法到 C++ 或类似的东西。

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

Answer 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。因为您甚至无法访问 79
20 秒内传输 TB 字节，您不太可能满足这种特殊情况下的速度要求。

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

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

矩阵的（整数）条目将呈指数增长，可能太快而难以处理。如果是这种情况，请执行以下操作
非常相同的计算，但是对几个中等大小的素数 p 取模 p。这将使您获得
对于各种 p，您的答案以 p 为模，而不使用 bigint 矩阵。使用足够的素数后，您就了解了他们的产品
比你的答案大，你可以用所谓的“中国剩余定理”来恢复
你的答案来自你的 mod-p 答案。

Answer 3

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

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

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

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

3. 模运算的成本很高，乘法的成本也较低。通过使用位置环切换颜色环，可以将乘法和模数的数量减少大约 C=100 倍。这允许您在进行乘法和取模之前将多次调用solve() 的返回值相加。

测试解决方案性能的一个好方法是使用病态案例。以下可能尤其令人畏惧：长度 10^15、C=100、素数块大小。

希望这有帮助。

Answer 4

在上面的答案中，

    ans += 1
    ans %= 100000007

如果没有一般模数，可能会更快：

    ans += 1
    if ans == 100000007 then ans = 0

Answer 5

请参阅 TopCoder 线程了解解决方案。没有人能够足够接近地在该线程中找到答案。