まず、10 ^ 100> Nであるため、各色のブロック数は完全な赤ニシンであることに注意してください。したがって、各色のブロックの数は実質的に無限です。
pここで、各位置に（有効な構成がある場合、スペースを残さないなど）、色のブロックが必要であることに注意してくださいc。このブロックを置く方法はいくつかありlen[c]ます。そのため、このブロックはまだこの位置にありpます。
私の考えは、すべての可能な色と位置を固定位置で試すことです（N/2範囲が半分になるため）。その後、それぞれの場合について、bこの固定色ブロックの前とこの固定色ブロックの後にセルがありaます。したがって、セルways(i)を並べて表示する方法の数を返す関数を定義すると（を使用）。次に、ある位置に固定されたカラーブロックで多数のセルを並べて表示する方法の数はです。考えられるすべての構成を合計すると、の答えが得られます。iways(0)=1ways(b)*ways(a)ways(i)
N/2範囲が半分になり、ほとんどの場合範囲を半分にできるので、固定位置を選択しましたceil(log(N))。ここで、ブロックを移動しているので、からをN/2計算する必要があります。ここで、はブロックが持つことができる最大の長さです。したがって、最終的な答えを得るには、長さについて（分散のためにもう少し）計算する必要があります。N/2-750N/2-750750750*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した長さのブロックでテストを実行すると、約要素が含まれます。これは、の非ルックアップビットがほぼ同じ回数呼び出されることを意味します。750memoise60000solve(n)