Помогите решить задачу на дп пожалуйста

Рейтинг: 3Ответов: 1Опубликовано: 19.07.2023

Кузнечик сидит на кочке с номером 1. Он хочет добраться до кочки номер n. С каждой кочки кузнечик может прыгать в кочку с номером на 1 или на 3 больше текущей. Каким количеством способов кузнечик может добраться из первой кочку на кочку номер n? Так как ответ может быть слишком большим, выведите его по модулю 10^9+7

Входные данные В единственной строке дано целое число n (1≤n≤10^6)

Выходные данные Выведите ответ по модулю 10^9+7

Пишет неправильный ответ на тесте

Мой код:'''

#include <iostream>
#include<vector>

int main()
{
    int n;
    std::cin >> n;
    std::vector<unsigned long long> F(n, 0);
    F[0] = 1;
    F[1] = 1;
    F[2] = 1;
    for (int i = 3; i < n; i++) {
        F[i] = F[i - 1] + F[i - 3];
    }
    std::cout << F[n - 1] % 1000000007;
    return 0;
}

'''

c# динамическое-программирование
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Попробуйте приравнивать F[i] к остатку от деления на 10^9+7 на каждой итерации цикла for (скорее всего у вас просто получается слишком большое число, выходящее за границы типа)

for (int i = 3; i < n; i++) {
        F[i] = (F[i - 1] + F[i - 3]) % (1e9+7);
}

cout << F[n - 1];

Примерно так. Также, в дальнейшем вообще не советую в cout делать подобные операции, он их может неправильно интерпретировать и вывести абсолютно неожиданный для вас ответ.

В остальном же, у вас все нормально.