编程问题 - 块

Question

的游戏也许你会对如何解决以下problem的想法。

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

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

这个问题应该在20秒内解决T < = 25个测试用例。答案应该是MOD 100000007（素数）。

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

Answer 1

请参阅TopCoder thread寻求解决方案。没有人足够接近在这个线程中找到答案。

Answer 2

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

现在请注意，在每个位置p（如果存在有效配置，不会留下空格等）必须阻止颜色，c。这个区块有说谎的方式len[c]，所以它仍然在这个位置上，p。

我的想法是尝试在固定位置（N/2因为它半部的范围内）的所有可能的颜色和位置，然后对每一种情况下，存在该固定颜色块之后这个固定的彩色块和a之前b细胞。因此，如果我们定义一个函数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))（多一点因为方差）长度才能得到最终答案。

所以为了让你有memoisation要通过良好的表现，因为这本质上是一种递归算法。

所以使用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++或其他。

EDIT：运行与N = 10^15测试和块长度为750我得到memoise包含有关60000元件，这意味着非查找solve(n)位称为大约相同数量的时间。

Answer 3

请注意：在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 terabytes的存储要求。由于您在20秒内甚至无法访问兆兆字节，因此在这种特殊情况下不太可能满足速度要求。

你最好的希望发生在C不是太大，而leni对于我来说都很大。在这种情况下，答案是 仍然与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 4

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

我想建议了一些改进，将进一步加快速度：

1. 而不是去在中间的块可以定位的所有方式的，你只需要看一遍上半部分，并将解乘以2.这是因为后半部分是对称的。对于奇数长度的块，您仍然需要将居中位置作为一个单独的情况。

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

3. 模数运算很昂贵，乘法运算的次数也较少。通过用位置环切换色彩循环，乘法和模数可减少约C = 100倍。这使您可以在执行乘法和模数前将几个调用的返回值添加到solve（）中。

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

希望这会有所帮助。

Answer 5

在上面的回答

ans += 1 
    ans %= 100000007 

可能会快很多不一般的模数：

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