задача на алгоритмическое программирование

@supermegahaxer · Регистрация: 29.03.2020

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

Ограничение времени 2 секунды
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
В современных системах при генерации паролей часто пытаются добиться запоминаемости.
В новой операционной системе «Унас» все пароли являются кириллическими. Используются 33 буквы кириллицы, из них 10 букв являются гласными, 21 — согласными; твёрдый и мягкий знаки являются специальными буквами.
Для запоминаемости используются следующие правила:

Мягкий и твёрдый знак можно использовать только после согласных (кроме “й”); эти знаки не могут идти ни перед какой согласной.
Рядом с гласными не должно быть других гласных, рядом с согласными — других согласных.
Вычислите, какое количество паролей длины N является запоминающимися.

Формат ввода
Входные данные содержат одно целое число
N (1 ≤N≤10^6) — длина пароля
Формат вывода
Выведите одно целое число — остаток от деления количества запомниающихся паролей длины N на 10^9+9.
Пример
Ввод Вывод
2 460

при 2 должно быть 460, но у меня почему-то получается 462... вроде динамика верно написана, надеюсь на вашу помощь

C++

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
 
const int M = 1e9 + 9;
 
ll mod(ll d) {
    return ((d % M) + M) % M; }
 
long long mmul (ll x, ll y) {
    return mod(mod(x) * mod(y)); }
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>>dp(n + 1, vector<int>(3));
    dp[1][1] = 21;
    dp[1][2] = 10;
    for (int i = 2; i <= n; i++)
    {
        dp[i][1] = mmul(mod(dp[i - 1][2]) - mmul(dp[i - 2][1], 2), 21);
        dp[i][2] = mmul(mod((mod(dp[i - 1][1]) - mod(dp[i - 2][2]))), 12);
    }
    cout << mod(mod(dp[n][1]) + mod(dp[n][2])) - n;
}

Добавлено через 7 минут

C++

1	cout << mod(mod(dp[n][1]) + mod(dp[n][2])) - n;

забыл, сказать, что "- n" - это я тупо пытался подгонять, к алгоритму никакого отношения не имеет

	12.12.2020, 16:07