编程问题 - 块游戏

Question

也许你会对如何解决以下问题有所了解.

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

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

对于T <= 25个测试用例,该问题应在20秒内解决.应该计算答案MOD 100000007(素数).

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

Answer 1

首先要注意的是,每种颜色的块数都是一个完整的红色鲱鱼,因为总是10 ^ 100> N. 因此每种颜色的块数实际上是无限的.

现在请注意,在每个位置,p(如果有一个有效的配置,不留空格等)必须阻止颜色,c.有这种len[c]方法可以说谎,所以它仍然位于这个位置上,p.

我的想法是在固定位置尝试所有可能的颜色和位置(N/2因为它将范围减半),然后对于每种情况,b在此固定颜色块之前和a此固定颜色块之后存在单元格.因此,如果我们定义一个ways(i)返回tile i单元格的方法的函数(with 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++或其他类似的.

编辑:运行一个测试N = 10^15和一个长度的块750我得到的memoise包含有关60000元素,这意味着非查找位solve(n)被调用大约相同的时间.