Задача

Вычислить количество последовательностей длины $n,$ состоящих только из нулей и единиц, в которых не встречается три единицы подряд.

Входные данные

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

Выходные данные

Вывести количество искомых последовательностей по модулю $12345.$

Тесты

Входные данные	Выходные данные
$1$	$2$
$4$	$0$
$263$	$10159$
$10000$	$8872$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int MAX = 100010;
	static int f[] = new int[MAX];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		f[1] = 2; 
		f[2] = 4; 
		f[3] = 7;
		for(int i = 4; i <= n; i++) {
			f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
		}
		System.out.println(f[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static int MAX = 100010;

static int f[] = new int[MAX];

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

f[1] = 2;

f[2] = 4;

f[3] = 7;

for(int i = 4; i <= n; i++) {

f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

}

System.out.println(f[n]);

}

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

Код программы

import java.util.Scanner;

public class Main {
    public static long binPow(long a, long b, int m) {
        a %= m;
        if (b == 0) return 1;
        else if (b % 2 == 0) {
            return binPow((a * a) % m, b / 2, m);
        }
        else return (a * binPow(a, b - 1, m)) % m;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        int m = scanner.nextInt();
        System.out.println(binPow(a, b, m));
    }
}

import java.util.Scanner;

public class Main {

public static long binPow(long a, long b, int m) {

a %= m;

if (b == 0) return 1;

else if (b % 2 == 0) {

return binPow((a * a) % m, b / 2, m);

}

else return (a * binPow(a, b - 1, m)) % m;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong();

long b = scanner.nextLong();

int m = scanner.nextInt();

System.out.println(binPow(a, b, m));

}

Решение задачи

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\\\ \text{ при } B \equiv 1 \pmod 2\\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: рекуррентная формула

e-olymp 263. Три единицы

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

e-olymp 480. Возведение в степень — 2

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки