Решение задачи Тетраэдр с Codeforces

Без пояснения   Просмотров: 123

Вам задан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.
В вершине тетраэдра D находится муравей. Муравей очень подвижный и не любит стоять на месте. В каждый момент времени он совершает один шаг от одной вершины к другой по некоторому ребру тетраэдра, оставаться на месте он не может.

От Вас в этой задаче требуется совсем немногое: нужно посчитать каким количеством способов муравей может прийти из исходной вершины D в себя ровно за n шагов. Другими словами, Вас просят узнать количество различных циклических путей длины n из вершины D в себя. Поскольку это количество может быть достаточно большим, ответ требуется посчитать по модулю 1000000007 (109 + 7).

Код 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int main()
{
	ll n;
	cin>>n;
	ll x = 0,y = 1;
	for(int i=0;i<n-1;i++)
	{
		ll a = x;
		x = (3 * y)%mod;
		y = (a + 2 * y)%mod;
	}
	cout<<x<<endl;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта