Получил 28 сек (ускорил на 7 сек), заменив все xrange на range
+ заменил вложенные циклы product'ом + добавил условия в генераторах. Больше скорости я выжать не смог.from itertools import product #import time #import sys #sys.stdin, sys.stdout = open("aplusb.in", "r"), open("aplusb.out", "w") #begin = time.time() MOD = 10**9+7 #c = map(int, raw_input()[::-1]) c = [9]*10000 n = len(c) r10, rn, r1_n, r2, r1_10 = range(10), range(n), range(1, n), range(2), range(1, 10) s = [[[[0, 0] for j in r10] for i in r10] for k in rn] for i in range(c[0]+1): s[0][i][c[0]-i][0] = 1 for i in range(c[0]+1, 10): s[0][i][10+c[0]-i][1] = 1 for k, i, j, p, p0 in product(r1_n, r10, r10, r2, r2): if i+j == c[k]+10*p-p0: s[k][i][j][p] = sum( s[k-1][x][y][p0] for x in r10 if x != i for y in r10 if y != j and s[k-1][x][y][p0])%MOD print sum(s[-1][i][j][0] for i, j in product(r1_10, r1_10) if s[-1][i][j][0])%MOD #print time.time()-begin
Вариант со смещениями ушел в аут (52 сек) + я его еще коряво реализовал (ответ некорректный выдавал).
Ну придется теперь решать “числодробительные задачи” на c++
Остальные все равно на Python'е буду решать ^^. Очень уж элегантно решения задач выглядят+длинная арифметика и много других вкусняшек из под коробки.