Задача с++. Интересно увидеть варианты решения с разных языков

Question

Вам задан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.

Начинаем шаги с вершины D. Нужно делать по одному шагу по ребру тетраэдра. Сколько есть способов, чтобы прийти из исходной вершины D в себя за n шагов.

Формат входных данных Целое число n (1 ≤ n ≤ 107) — требуемая длина циклического пути.

Формат результата Количество способов по модулю 1000000007 (109 + 7).

Пример: Входные данные: 2 Результат: 3

Входные данные: 4 Результат: 21

Искомые пути в первом примере: • D - A - D • D - B - D • D - C - D

Answer 1

Типичное ДП.

За N ходов попасть в D из D - утроенное количество способов попасть из не-D в D за n-1 ход.
За N ходов попасть в D из не-D - удвоенное количество способов попасть из не-D в не-D за n-1 ход + количество способов попасть за n-1 ход из D в D.

int r[2][10000001] = {};
const unsigned int M = 1000000000+7;

int main()
{
    unsigned int n;
    cin >> n;

    r[0][0] = r[1][0] = 0;
    r[1][1] = 0;
    r[0][1] = 1;

    for(unsigned int i = 2; i <= n; ++i)
    {
        r[1][i] = 3*r[0][i-1]%M;
        r[0][i] = (r[1][i-1]+2*r[0][i-1])%M;
    }

    cout << r[1][n] << endl;
}

Впрочем, есть варианты и попроще, например,

int cnt(unsigned int n)
{
    n--;
    int a = 0;
    for(int i = 3;n-->0;i=-i) a = (3*a+i)%M;
    return a;
}

Answer 2

Есть такая штука - число путей длиной k между вершинами графа есть число на пересечении соответствующих столбца и строки в матрице смежности, возведённой в k-ю степень. Таким образом, за логарифмическое (при использовании метода возведения в степень matrix squaring) время можно найти искомое значение.

import numpy
from numpy.linalg import matrix_power

a = numpy.array([[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]])
for i in range(2, 15):
   b = matrix_power(a, i)
   print(i, b[0][0], numways(i))

2 3 3
3 6 6
4 21 21
5 60 60
6 183 183
7 546 546
8 1641 1641
9 4920 4920
10 14763 14763
11 44286 44286
12 132861 132861
13 398580 398580
14 1195743 1195743

Если посмотреть на результаты, то можно заметить закономерность - число путей растет примерно в три раза при увеличении длины на единицу. Получается несложная формула (numways) за константное время, используя поправку на чётность числа (кстати, вот её где можно найти в разделе FORMULA, а пониже рекуррентное соотношение, которое Harry получил). Для оптимизации избегаем появления длинных чисел, используя возведение в степень по модулю (numwaysmod)

def numways(n):
    return ((3**n + 3*(1-2*(n%2))) // 4) % 1000000007

def numwaysmod(n):
    if n%2:
       return((pow(3, n, 4*1000000007) + 4*1000000007-1)%(4*1000000007))//4
    else:
       return((pow(3, n, 4*1000000007) + 4)%(4*1000000007))//4

БЛОГ НА HUSL

Задача с++. Интересно увидеть варианты решения с разных языков

Ответы (2 шт):