Их опять двое

@Азиз02 · Регистрация: 16.01.2025

Студворк — интернет-сервис помощи студентам

Здравствуйте . помогите пожалуйста написать код .
Есть два кузнечика им надо залесть на лестницу с n количеством ступенек . они могут прыгать на 1,2,3 лесенки . они не должны прыгать на одну и туже ступеньку . водится 1 число (4≤n≥10⁷)
Количество ступеней .надо вывести одно число . показывающее количество путей.так как число может быть большим выведи ответ по модулю 998244353.

F. Их теперь двое
Все языки Python 3.9 (PyPy 7.3.16)
Ограничение времени 1 секунда 6 секунд
Ограничение памяти 1024 Мб 2048 Мб
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
В далеком будущем, когда цифровые технологии и искусственный интеллект стали неотъемлемой частью повседневной жизни, задачи на логическое мышление трансформировались, став более интригующими и сложными. Вспоминая классическую задачу о кузнечике, где нужно было подсчитать количество маршрутов до вершины лестницы, современные мыслители создали новую версию этой головоломки, включив в нее два интеллектуальных агента.

Эти два "кузнечика" в цифровом Мегаполисе способны прыгать на 1, 2 или 3 ступеньки, когда они поднимаются по n-ступенчатой лестнице, но есть одно важное правило: ни один из них не должен наступить на ту же ступеньку, что и другой в каком-либо сценарии. Это означает, что как только один кузнечик побывал на определенной ступени, второй не может использовать ее в своей последовательности (кроме стартовой и конечной ступеньки).

Цель состоит в том, чтобы вычислить, сколько различных стратегий или путей существует, чтобы эти интеллектуальные агенты, следуя своим прыжковым ограничениям, смогли достичь вершины. Таким образом, задача становится не только тестом на их неповторимые способности, но и символом согласованности и синхронизации действий в сложных системах. Смогут ли они достичь своей цели, избегая пересечений и действуя как единое целое? Это и является вызовом в нашем технологичном и инновационном мире.

Формат ввода
Первая строка содержит единственное целое число
N
(4≤N≤10⁷) — количество ступеней.

Формат вывода
Выведите единственное число — количество путей для двух кузнечиков. Так как число может быть очень большим, выведите ответ по модулю 998244353.

@Red white socks · 18.01.2025, 13:07

Сообщение от Азиз02

Их опять двое

Не по теме:

Я понял причину ваших затруднений. У вас по Фрейду слово "опять" вместо "теперь". Смотрите назад, а не здесь и сейчас. В прошлое вместо настоящего и будущего. Следует поменять парадигму мышления. Поразмыслите над этим.

Расскажу решение, которое считает за логарифм.
Изначально в задаче есть неопределенность с начальным и конечным положением кузнечиков, а тесты, чтобы ее устранить не приведены. Я буду считать, что последняя ступенька является финишем (n - конечное положение), а на старте кузнечики на земле (начальное положение - 0).
Разобьём ступеньки на блоки по 3 штуки. Старт и финиш в блок не входят. Предпоследняя ступенька входит всегда. Соответственно в зависимости от остатка при делении n на 3 в блок также могут не войти до 2 первых ступенек.
Например,
при n = 4 ступеньки 1, 2, 3 объединяются в блок, ступенька 4 - финиш.
при n = 5 в блоке ступеньки 2, 3, 4, ступенька 5 - финиш.
при n = 12 будет 3 блока: (3, 4, 5), (6, 7, 8), (9, 10, 11), 12 - финиш, а ступеньки 1 и 2 в блок не вошли.
Назовем состоянием блока упорядоченную пару номеров ступенек блока (от 1 до 3), на которые могут запрыгнуть кузнечики. Всего возможно 6 состояний, занумеруем их так:

Code
1
2
3
4
5
6
1: (1, 2)
2: (2, 1)
3: (1, 3)
4: (3, 1)
5: (2, 3)
6: (3, 2)

Также будем считать, что кузнечики прыгают следующим образом: если находятся в одном блоке, то прыгают одновременно, если в разных, то один кузнечик стоит и ждет "отстающего".
Пусть есть произвольный валидный маршрут прыжков. Тогда для каждого блока есть ход, после которого оба кузнечика находятся в этом блоке и этот ход единственный (последнее не принципиально, но облегчает понимание связи с состоянием блока)
Назовем матрицей перехода матрицу размером 6x6, где на пересечении i-й строки и j-го столбца число вариантов перехода из i-го состояния в j-е состояние следующего блока.
Например, из состояния 1: (1, 2) в состояние 1: (1, 2) можно прийти 3 вариантами ходов:
(1, 2) -> (1, 2)
(1, 2) -> (3, 2) -> (1, 2)
(1, 2) -> (1, 3) -> (1, 2)
Следовательно a_11 = 3.
При желании можно и код написать, подсчитывающий эту матрицу и кажется, что вручную трудоемко, но выписать всю матрицу у меня заняло от силы 5 минут.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?A =\begin{bmatrix} 3 & 1 & 1 & 1 & 0 & 1 \\ 1 & 3 & 1 & 1 & 1 & 0 \\ 2 & 1 & 2 & 0 & 1 & 0 \\ 1 & 2 & 0 & 2 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$

Тогда итоговое число комбинаций равно
$https://www.cyberforum.ru/cgi-bin/latex.cgi? N = b^T A^{m-1} c$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?b = (b_i)$ - вектор-столбец, равный количеству комбинаций перейти из стартовой позиции в i-е состояние первого блока, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?c = (c_i)$ - вектор-столбец, равный количеству комбинаций перейти из i-го состояния последнего блока к финишу, $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ - число блоков.
Столбец c легко выписать
$https://www.cyberforum.ru/cgi-bin/latex.cgi?c =\begin{bmatrix} 3 \\ 3 \\ 2 \\ 2 \\ 1 \\ 1 \end{bmatrix}$
Столбец b же зависит от числа ступенек перед первым блоком, т.е. от остатка деления n на 3.
Например, если ступенек перед первым блоком нет, т.е. n = 3k+1, то
$https://www.cyberforum.ru/cgi-bin/latex.cgi?b =\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$
Остальные 2 варианта оставляю вам.
Ну вот вроде бы и всё. Все вычисления по указанному модулю. Возведение в степень (неважно, числа или матрицы) бинарным алгоритмом производится за логарифм. В формуле произведение матриц, но, как можно заметить, в результате выходит скаляр.

Замечание 1. Это всё кажется сложным, но если знакомы цепи Марковы из случайных процессов, то здесь все по аналогиии, только вместо вероятностей - комбинации.
Замечание 2. Вполне допускаю, что дальнейшим анализом, либо вычислением другим путем можно прийти к какой-то возможно простой формуле от n, но я решил остановиться на этом этапе.
Замечание 3. Код сознательно не пишу, поскольку 99% в этом решении именно математика, а закодить формулу никакого труда не стоит. Но возможно решение и чисто программистское, через ДП, правда оно уже будет за линию (но в 6с на питоне должно укладываться).

@vamspa · 20.01.2025, 21:59

Знакомый код написал, пояснить не смогу. Может можно и проще сделать.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def solve():
    mod = 998244353
    n = int(input())
    L = 200
    f = [0]*(L+1)
    f[0] = 1
    for i in range(1, L+1):
        a = f[i-1] if i-1>=0 else 0
        b = f[i-2] if i-2>=0 else 0
        c = f[i-3] if i-3>=0 else 0
        f[i] = (a+b+c) % mod
    dp = [0]*(L+1)
    dp[0] = 1
    for nn in range(1, L+1):
        s = 0
        for k in range(1, nn):
            s += dp[k] * (f[nn-k]*f[nn-k] % mod)
            s %= mod
        dp[nn] = (f[nn]*f[nn] - s) % mod
    if n <= L:
        print(dp[n] % mod)
        return
    def berlekamp_massey(s):
        n = len(s)
        C = [1]
        B = [1]
        L = 0
        m = 1
        b = 1
        for i in range(n):
            d = s[i]
            for j in range(1, L+1): d = (d + C[j]*s[i-j]) % mod
            if d == 0: m += 1
            else:
                T = C[:]
                coeff = d * pow(b, mod-2, mod) % mod
                if len(C) < len(B) + m:
                    C += [0] * (len(B) + m - len(C))
                for j in range(len(B)):
                    C[j+m] = (C[j+m] - coeff*B[j]) % mod
                if 2*L <= i:
                    L = i+1 - L
                    B = T
                    b = d
                    m = 1
                else: m += 1
        return C[:L+1]
    
    bm = berlekamp_massey(dp[:L+1])
    coefs = [(-bm[i]) % mod for i in range(1, len(bm))]
    s_init = dp[:len(coefs)]
    
    def kitamasa(coefs, s, n):
        L = len(coefs)
        def combine(p, q):
            r = [0]*(2*L-1)
            for i in range(L):
                ai = p[i]
                if ai == 0: continue
                for j in range(L):
                    r[i+j] = (r[i+j] + ai*q[j]) % mod
            for i in range(2*L-2, L-1, -1):
                ri = r[i]
                if ri == 0: continue
                for j in range(1, L+1):
                    r[i-j] = (r[i-j] + ri*coefs[j-1]) % mod
            return r[:L]
        res = [1] + [0]*(L-1)
        base = [0]*L
        if L > 1: base[1] = 1
        else: base[0] = coefs[0]
        exp = n
        while exp:
            if exp & 1: res = combine(res, base)
            base = combine(base, base)
            exp //= 2
        result = 0
        for i in range(L):
            result = (result + res[i]*s[i]) % mod
        return result
    print(kitamasa(coefs, s_init, n) % mod)
solve()

@Азиз02 · 20.01.2025, 22:19 **[ТС]**

Огромное спасибо . извините а видео или объяснение есть ? Я просто эту задачу решить не мог и хочу понять как ее решить. Еще раз спасибо

@vamspa · 20.01.2025, 22:24

К сожалению объяснения нет

@Азиз02 · 20.01.2025, 22:29 **[ТС]**

Хорошо спасибо .

@Red white socks · 21.01.2025, 10:37

Сообщение от Азиз02

Я просто эту задачу решить не мог и хочу понять как ее решить.

То есть подробное решение (и более эффективное) вас не удовлетворило?
Запилю по нему код, со всеми проверками, если расскажете откуда задача.

Добавлено через 2 часа 25 минут

Сообщение от Red white socks

и более эффективное

Каюсь, тут решение за константу (меня смутил for i in range(n)), но здесь действительно высшая математика. Более менее понятно, что происходит, но почему это приводит к правильному ответу (совпадает и с моим решением) - тут очень серьезная теория.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Азиз02 0 / 0 / 0 Регистрация: 16.01.2025 Сообщений: 3

	Их опять двое 16.01.2025, 19:15. Показов 2862. Ответов 6 Метки нет (Все метки) Здравствуйте . помогите пожалуйста написать код . Есть два кузнечика им надо залесть на лестницу с n количеством ступенек . они могут прыгать на 1,2,3 лесенки . они не должны прыгать на одну и туже ступеньку . водится 1 число (4≤n≥10⁷) Количество ступеней .надо вывести одно число . показывающее количество путей.так как число может быть большим выведи ответ по модулю 998244353. F. Их теперь двое Все языки Python 3.9 (PyPy 7.3.16) Ограничение времени 1 секунда 6 секунд Ограничение памяти 1024 Мб 2048 Мб Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt В далеком будущем, когда цифровые технологии и искусственный интеллект стали неотъемлемой частью повседневной жизни, задачи на логическое мышление трансформировались, став более интригующими и сложными. Вспоминая классическую задачу о кузнечике, где нужно было подсчитать количество маршрутов до вершины лестницы, современные мыслители создали новую версию этой головоломки, включив в нее два интеллектуальных агента. Эти два "кузнечика" в цифровом Мегаполисе способны прыгать на 1, 2 или 3 ступеньки, когда они поднимаются по n-ступенчатой лестнице, но есть одно важное правило: ни один из них не должен наступить на ту же ступеньку, что и другой в каком-либо сценарии. Это означает, что как только один кузнечик побывал на определенной ступени, второй не может использовать ее в своей последовательности (кроме стартовой и конечной ступеньки). Цель состоит в том, чтобы вычислить, сколько различных стратегий или путей существует, чтобы эти интеллектуальные агенты, следуя своим прыжковым ограничениям, смогли достичь вершины. Таким образом, задача становится не только тестом на их неповторимые способности, но и символом согласованности и синхронизации действий в сложных системах. Смогут ли они достичь своей цели, избегая пересечений и действуя как единое целое? Это и является вызовом в нашем технологичном и инновационном мире. Формат ввода Первая строка содержит единственное целое число N (4≤N≤10⁷) — количество ступеней. Формат вывода Выведите единственное число — количество путей для двух кузнечиков. Так как число может быть очень большим, выведите ответ по модулю 998244353. 0

@Азиз02 0 / 0 / 0 Регистрация: 16.01.2025 Сообщений: 3
	20.01.2025, 22:19 [ТС]
	Огромное спасибо . извините а видео или объяснение есть ? Я просто эту задачу решить не мог и хочу понять как ее решить. Еще раз спасибо 0

@vamspa 0 / 0 / 0 Регистрация: 20.01.2025 Сообщений: 2
	20.01.2025, 22:24
	К сожалению объяснения нет 0

@Азиз02 0 / 0 / 0 Регистрация: 16.01.2025 Сообщений: 3
	20.01.2025, 22:29 [ТС]
	Хорошо спасибо . 0

Их опять двое

Решение