Вывод N-ого члена последовательности

@Fixer_84 · Регистрация: 30.04.2016

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

Здравствуйте, уважаемые форумчане! У меня опять несложный вопрос к тем кто разбирается. С модулями у меня плохо, поэтому обращаюсь сюда. Сама задача совсем несложная, но мне бы очень хотелось получить опыт того как это обычно делается правильно. Дана последовательность: 3, 8, 12, 17, 22, 28, 35, ... Необходимо вывести ее n-ый член по модулю 123456789. Ограничения на n: 1<=n<=10^11. Мне удалось вывести первые n членов и сделал я это довольно быстро пользуясь только операцией сложения. Но мне непонятно (раньше таких задач не решал) куда вставлять операцию mod 123456789 в моем коде, чтобы все посчитать правильно и уложится в ограничения? Очень прошу помочь решить этот несложный вопрос. Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    int n, a, b, sum, k;
    cin >> n;
    a = 3;
    b = 8;
    k = -1;
    while (n--) {
        cout << a << " ";
        sum = a + b - k;
        a = b;
        b = sum;
        k += 4;
    }
    system("pause");
    return 0;
}

@Fixer_84 · 05.08.2018, 18:04 **[ТС]**

no swear, здравствуйте! Спасибо за ваш ответ. Получилось написать программу для вывода n-ого члена последовательности. Куда, здесь, теперь нужно вставлять модуль? Я не до конца понял. Вот код:

C++
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
 
const int n = 4;
 
    using namespace std;
 
long long** matrixMultiply(long long** a, long long** b, long long n) //Функция переменожения двух матриц
{
    long long** c = new long long*[n];
    for (int i = 0; i < n; i++) {
        c[i] = new long long[n];
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            c[j][i] = 0;
            for (int r = 0; r < n; r++) {
                c[j][i] += a[j][r] * b[r][i];
            }
        }
    }
    return c;
    for (int i = 0; i < n; i++) {
        delete[] c[i];
    }
    delete[] c;
}
 
long long** multiplyVector(long long** a, long long** b, long long n) //Функция умножения вектора на матрицу
{
    long long** c = new long long*[1];
    for (int i = 0; i < 1; i++) {
        c[i] = new long long[n];
    }
    for (int j = 0; j < 1; j++) {
        for (int i = 0; i < n; i++) {
            c[j][i] = 0;
            for (int r = 0; r < n; r++) {
                c[j][i] += a[j][r] * b[r][i];
            }
        }
    }
    return c;
    for (int i = 0; i < 1; i++) {
        delete[] c[i];
    }
    delete[] c;
}
 
long long** matrixPower(long long** a, long long n, long long m) { //Бинарное возведение матрицы в степень (оптимизация)
    if (m == 1)
        return a;
    if (m % 2 == 1)
        return matrixMultiply(matrixPower(a, n, m - 1), a, n);
    else {
        a = matrixPower(a, n, m / 2);
        return matrixMultiply(a, a, n);
    }
}
 
int main() {
    long long m;
    long long** a = new long long*[n] { //Задаем матрицу перехода
        new long long[n] {0,  1,  0,  0},
        new long long[n] {1,  1,  0,  0},
        new long long[n] {0, -1,  1,  0},
        new long long[n] {0,  0,  1,  1}
    };
    long long** b = new long long*[1];
    for (int i = 0; i < 1; i++) {
        b[i] = new long long[n] {3, 8, -1, 4}; //Задаем начальный вектор
    }
    long long** c = new long long*[1];
    for (int i = 0; i < 1; i++) {
        c[i] = new long long[n];
    }
    cout << "Enter a matrix power (n-th element):\n";
    cout << "m = ";
    cin >> m; //Вводим степень матрицы (искомый n-ый член последовательности)
    a = matrixPower(a, n, --m);
    c = multiplyVector(b, a, n);
    cout << "Searched vector:\n"; //Выводим искомую матрицу
    for (int j = 0; j < n; j++) {
        cout << c[0][j] << " ";
    }
    cout << "\nN-th element: " << c[0][0] << "\n"; //Выводим искомый член последовательности
    for (int i = 0; i < n; i++) {
        delete[] a[i];
    }
    delete[] a;
    for (int i = 0; i < 1; i++) {
        delete [] b[i];
    }
    delete [] b;
    for (int i = 0; i < 1; i++) {
        delete [] c[i];
    }
    delete [] c;
    system("pause");
    return 0;
}

@no swear · 05.08.2018, 18:41

Строка 17

C++
1
c[j][i] = (c[j][i] + a[j][r] * b[r][i]) % 123456789;

И строка 85

C++
1
cout << "\nN-th element: " << c[0][0] % 123456789 << "\n";

@Fixer_84 · 05.08.2018, 20:20 **[ТС]**

no swear, спасибо огромное за помощь! Решение ниже принимают. Попробую сократить код...

C++
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
#include <bits/stdc++.h>
 
    const int n = 4;
 
using namespace std;
 
long long** matrixMultiply(long long** a, long long** b, long long p, long long n) {
    long long** c = new long long*[p];
    for (int i = 0; i < p; i++) {
        c[i] = new long long[n];
    }
    for (int j = 0; j < p; j++) {
        for (int i = 0; i < n; i++) {
            c[j][i] = 0;
            for (int r = 0; r < n; r++) {
                c[j][i] = (c[j][i] + a[j][r] * b[r][i]) % 123456789;
            }
        }
    }
    return c;
    for (int i = 0; i < p; i++) {
        delete[] c[i];
    }
    delete[] c;
}
 
long long** matrixPower(long long** a, long long n, long long m) {
    if (m == 1)
        return a;
    if (m % 2 == 1)
        return matrixMultiply(matrixPower(a, n, m - 1), a, n, n);
    else {
        a = matrixPower(a, n, m / 2);
        return matrixMultiply(a, a, n, n);
    }
}
 
int main() {
    int t;
    long long m;
    cin >> t;
    for (int i = 0; i < t; i++) {
        long long** a = new long long*[n] {
            new long long[n] { 0,  1,  0,  0 },
            new long long[n] { 1,  1,  0,  0 },
            new long long[n] { 0, -1,  1,  0 },
            new long long[n] { 0,  0,  1,  1 }};
        long long** b = new long long*[1];
        for (int i = 0; i < 1; i++) {
            b[i] = new long long[n] { 3,  8,  -1,  4 };
        }
        long long** c = new long long*[1];
        for (int i = 0; i < 1; i++) {
            c[i] = new long long[n];
        }
        cin >> m;
        if (m == 1) cout << 3 << "\n";
        else {
            a = matrixPower(a, n, --m);
            c = matrixMultiply(b, a, 1, n);
            cout << c[0][0] % 1234546789 << "\n";
        }
        for (int i = 0; i < n; i++) {
            delete[] a[i];
        }
        delete [] a;
        for (int i = 0; i < 1; i++) {
            delete [] b[i];
        }
        delete [] b;
        for (int i = 0; i < 1; i++) {
            delete [] c[i];
        }
        delete [] c;
    }
    system("pause");
    return 0;
}

И большое спасибо Ромахе, что вывел формулу! Тему можно закрывать. Все тесты пройдены.

@woldemas · 05.08.2018, 20:28

Сообщение от Fixer_84

Долго думает даже для n = 1000000000. А время 0.1 сек на выполнение. Тут какая-то формула нужна. Вычислять все члены последовательности слишком долго, даже по модулю, но я не уверен. В задании сказано, что значение n, вроде как, можно модифицировать для более хорошего решения.

Для вывода общего члена последовательности можно воспользоваться z-преобразованием (производящими функциями). Так прямое z-преобразование вашей последовательности:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F(z)= \frac {3 z^2 +5z - \frac {z(5-z)} {(z-1)^2}} {z^2 - z -1}$
Следовательно формула общего члена:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?4n + 3 + (\frac 1 2 - \frac sqrt5 {10}) (\frac 1 2 - \frac sqrt5 2)^{n-1} + \frac sqrt5 5 (\frac 1 2 + \frac sqrt5 2)^n$
Так на всякий случай.

@Fixer_84 · 05.08.2018, 20:47 **[ТС]**

woldemas, здравствуйте! Спасибо за ваш ответ. Я эту ссылку сохраню. Если речь снова пойдет о таких последовательностях, буду пробовать применять описанные выше методы.

@no swear · 05.08.2018, 20:48

Сообщение от Fixer_84

спасибо огромное за помощь!

Всегда рад помочь

А решение задачки я возьму себе на заметку

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	05.08.2018, 20:47 [ТС]
	woldemas, здравствуйте! Спасибо за ваш ответ. Я эту ссылку сохраню. Если речь снова пойдет о таких последовательностях, буду пробовать применять описанные выше методы. 0