也许你会有一个关于如何解决以下问题的想法。
约翰决定给他的儿子约翰尼买一些数学玩具。他最喜欢的玩具之一是不同颜色的积木。约翰决定买C种不同颜色的积木每种颜色他都会买古戈（10^100）积木。所有相同颜色的块都有相同的长度。但是不同颜色的块在长度上可能不同。
约翰尼决定用这些积木建造一个大的1×n积木他想知道他有多少方法可以做到这一点。如果存在颜色不同的位置，则有两种方法被认为是不同的。该示例显示大小为5的红色块、大小为3的蓝色块和大小为3的绿色块。它表明有12种方法可以制作长度为11的大块。
每个测试用例以整数1≤c≤100开始。下一行由c整数组成ith整数1≤leni≤750表示ith颜色的长度。下一行是正整数N≤10^15。
对于tMOD 100000007（质数）。
它可以归结为矩阵求幂问题，利用problem算法和快速求幂可以在O（N^2.376*log（max（leni））中相对有效地求解但似乎需要一个更有效的算法，因为Coppersmith Winograd暗示了一个很大的常数因子。你还有别的想法吗？它可能是一个数论或分而治之的问题
最佳答案
首先要注意每种颜色的色块数是一个完整的红鲱鱼，因为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的长度（由于方差的原因，会多一点）才能得到最终的答案。
所以为了获得好的性能，你必须通过记忆，因为这是一个固有的递归算法。
所以使用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++或者SUMUUCH，它会达到20秒限制。
编辑：使用
750*ceil(log(N))和长度N = 10^15的块运行测试，我得到750包含大约memoise元素，这意味着调用60000的非查找位的时间大约相同。关于algorithm - 编程问题-积木游戏，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4048118/