腾讯笔试题

import sys if __name__ == "__main__":     T, K = map(int, sys.stdin.readline().strip().split())     lst = []     maxLen = 0     mod = 10 ** 9 + 7     for t in xrange(T):         line = map(int, sys.stdin.readline().strip().split())         lst.append(line)         maxLen = max(maxLen, line[-1])     l = [1 for _ in xrange(K)]     for i in xrange(K, maxLen + 1):         l.append(l[-1] + l[i-K])     for t in xrange(T):         a, b = lst[t]         print sum(l[a:b+1]) % mod 这个能100%

楼主能否讲下思路捏~我用c++，python看起来有点吃力，感谢~~~

能讲讲思路吗

楼上17行，100%的代码，我感觉跟我的思路差不多呀，但是我就超时了，谁能给我分析分析为啥速度差这么多？ # encoding: utf-8 import sys res_dict = {} max_key = 0 def search(length, k):   global max_key   res_dict[0] = 1   if max_key >= length:     return res_dict[length]   else:     start = max_key   start = max(1, start)   for length_tmp in range(start, length + 1):     res_dict[length_tmp] = res_dict[length_tmp-1]     if length_tmp - k >= 0:       res_dict[length_tmp] += res_dict[length_tmp-k]     res_dict[length_tmp] %= (1e9+7)   max_key = length   return res_dict[length] line = [int(val) for val in sys.stdin.readline().strip().split(' ')] t = line[0] k = line[1] for group_idx in range(t):   line = [int(val) for val in sys.stdin.readline().strip().split(' ')]   a = line[0]   b = line[1]   if k == 0:     print 1     continue   count = 0   for length in range(a, b+1):     count += search(length, k)   print int(count % (1e9+7))

sum这一步没必要，直接dp保存和，然后减起点就是区间了，然后最后一步再取模，反正python无现长

这题要取模的吗？题目好像没说？

感觉这题应该是有个推导出来的公式，可以只需要On时间内计算出来

result = sum(dp[a:b+1])%(int(10e9+7)) 加上这里就是n平方了