E. Tetrahedron

Explanation: tetrahedron, rachitJain

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	const int nx = 1e7 + 5;
	const int Mod = 1e9 + 7;
	//int dp[4][4][nx];
	//int DP[2][nx];
	int dp[2][nx];
	/*int solve(int s, int d, int st)
	{
	if (st == 0) {
	if (s == d) return 1;
	return 0;
	}
	int &ret = dp[s][d][st];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i <= 3; i++) {
	if (i == s) continue;
	ret += solve(i, d, st - 1);
	if (ret >= Mod) ans -= Mod;
	}
	return ret;
	}
	int solve(int same, int steps)
	{
	if (steps == 1) {
	if (same) return 0;
	return 1;
	}
	int &ret = DP[same][steps];
	if (ret != -1) return ret;
	ret = 0;
	if (same == 1) return ret = (3LL * solve(1 - same, steps - 1)) % Mod;
	else ret = (2LL * solve(0, steps - 1) + solve(1, steps - 1)) % Mod;
	}*/
	void solve(int n)
	{
	ll last = 3, sec_last = 0, present;
	if (n == 1) cout << sec_last << endl;
	else if (n == 2) cout << last << endl;
	else {
	for (int i = 3; i <= n; i++) {
	present = ((2 * last) % Mod + (3 * sec_last) % Mod) % Mod;
	sec_last = last; // f(i - 2) = f(i - 1);
	last = present; // f(i - 1) = f(i)
	}
	cout << present % Mod << endl;
	}
	return;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	// solve(n);
	//return 0;
	//memset(dp, -1, sizeof dp);
	// memset(DP, -1, sizeof DP);
	//cout << solve(1, n) << endl;
	dp[1][0] = 1;
	for (int steps = 1; steps < nx; steps++) {
	dp[1][steps] = (3LL * dp[0][steps - 1]) % Mod;
	dp[0][steps] = (2LL * dp[0][steps - 1] + dp[1][steps - 1]) % Mod;
	}
	cout << dp[1][n] << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw tetrahedron.cpp hosted with ❤ by GitHub

Share: