| 1 Шахмуратов Артур Тимурович, 09 июня 2026 г. 16:51:05 |
| через гальминтона кэли ускорил до O(n) import sys sys.set_int_max_str_digits(300000) def poly_multiply_and_mod(A, B, m): deg_A = len(A) - 1 deg_B = len(B) - 1 C = [0] * (deg_A + deg_B + 1) for i in range(len(A)): if A[i] == 0: continue for j in range(len(B)): C[i + j] += A[i] * B[j] for i in range(len(C) - 1, m - 1, -1): if C[i] == 0: continue lead = C[i] C[i - 1] += lead C[i - m] += lead C[i] = 0 while len(C) > 1 and C[-1] == 0: C.pop() return C with open("INPUT.TXT", "r") as f: data = f.read().split() if data: m = int(data[0]) n = int(data[1]) if n < m: ans = 1 else: res = [1] base = [0, 1] p = n while p > 0: if p % 2 == 1: res = poly_multiply_and_mod(res, base, m)
|
|
|
| 2 Шахмуратов Артур Тимурович, 09 июня 2026 г. 16:47:02 |
| ну тут самое легкое это быстрое возведение матрицы переходов в степень. сложность nlognlogm причем тут динамика непонятно. и п.с сложность по моему недооценена import sys sys.set_int_max_str_digits(300000) def multiply_matrices(A, B): m = len(A) C = [[0] * m for _ in range(m)] for i in range(m): for k in range(m): if A[i][k] == 0: continue for j in range(m): C[i][j] += A[i][k] * B[k][j] return C def power_matrix(A, p): m = len(A) res = [[0] * m for _ in range(m)] for i in range(m): res[i][i] = 1 while p > 0: if p % 2 == 1: res = multiply_matrices(res, A) A = multiply_matrices(A, A) p //= 2 return res with open("INPUT.TXT", "r") as f: data = f.read().split() if data: m = int(data[0]) n = int(data[1]) if n < m: ans = 1 else: T = [[0] * m for _ in range(m)]
|
|
|
| 3 Аскаров Айдын Нурлыбекович, 15 августа 2017 г. 9:21:41 |
| Подскажите хорошую книгу п связи комбинаоики и динамики. Я Формулу комбинторики вывел, но мне трудно его перевести в ДП.
|
|
|
| 4 Маймаш Дастан, 21 января 2016 г. 13:37:28 |
| динамика =)
|
|
|
| 5 Некий Неизвестный, 07 ноября 2014 г. 19:48:20 |
| Почему динамика? Тут комбинаторика заходит за 0.007, да подумать надо немножко, но решение простое.
|
|
|
| 6 Хрушков Павел Вадимович, 20 января 2013 г. 4:58:35 |
| Задача очень похожа на старого-доброго кузнечика (зайчика) )
|
|
|
| 7 Акылбек, 14 февраля 2012 г. 15:53:46 |
| Над задачкой пришлось много думать, пока не нашёл динамическое решение :). Времени ушло много, а кода я написал мало ;)
|
|
|
| 8 Ефанов Владимир Алексеевич, 25 августа 2010 г. 19:53:20 |
| 3 9 => 19
|
|
|
| 9 Атаян Гарик Артурович, 18 августа 2010 г. 18:31:41 |
m=21 n=25 =>6
m=21 n=27 =>8
:)
|
|
|
| 10 Мас Мих В, 12 февраля 2010 г. 15:40:27 |
| а почему раздел не комбинаторика?
|
|
|
| 11 Охотников Григорий Иванович, 16 октября 2009 г. 8:55:15 |
| Просто увеличил размеры типа - Accepted!
|
|
|
| 12 Масюк Олег Юрьевич, 16 января 2009 г. 14:06:28 |
Тут заполняется матрица наподобии треугольника паскаля, или нет?
Думаю, что тут все более линейно.
|
|
|
| 13 Ладик Артём, 16 октября 2008 г. 16:55:28 |
Приведите пожалйста несколько примеров, где n и m примерно около 10
8 11 => 5; 7 13 => 8; 9 12 => 5
|
|
|
| 14 Ладик Артём, 15 октября 2008 г. 23:14:03 |
скажите для 2 50 ответ такой 1817497480 ??????
Для M=2 и N=50 должно получаться 20365011074 вариантов. Обратите внимание: это число не помещается в 4-байтовое целое, возможно ошибка заключается в неверном выборе типа переменной для хранения результата?
|
|
|
