Submission #4709080

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <math.h>
#include <time.h>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end() 
#define PII pair <ll,ll>
#define N 100005
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

ll A[65][65];
map <string, int> m;
map <int, string> rm;
void map_possibilities()
{
	int x = 1;
	for (int i = 1; i <= 4; ++i)
	{
		for (int j = 1; j <= 4; ++j)
		{
			for (int k = 1; k <= 4; ++k)
			{
				int val = i * 100 + j * 10 + k;
				string s = to_string(val);
				m[s] = x;
				rm[x] = s;
				x++;
			}
		}
	}
}
bool valid(string s)
{
	int n = (int) s.size();
	if(s.find("132") != string::npos)
		return false;
	for (int i = 0; i < n - 1; ++i)
	{
		swap(s[i], s[i + 1]);
		if(s.find("132") != string::npos)
			return false;
		swap(s[i], s[i + 1]);
	}
	return true;
}
void calc_matrix()
{
	string s, t;
	int cnt = 0;
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			s = rm[i], t = rm[j];
			if(s[1] != t[0] || s[2] != t[1])
				continue;
			s.push_back(t.back());
			if(valid(s))
			{
				A[j][i] = 1;
			}
		}
	}
}
void matrix_mul(ll x[][65], ll y[][65])
{
	ll c[65][65];
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			for (int k = 1; k <= 64; ++k)
			{
				c[i][j] += x[i][k] * y[k][j];
				c[i][j] %= MOD;
			}
		}
	}
	for (int i = 1; i <= 64; ++i)
		for (int j = 1; j <= 64; ++j)
			x[i][j] = c[i][j];
}
ll matrix_expo(ll mat[][65], int b)
{
	ll res[65][65], cnt = 0;
	memset(res, 0, sizeof(res));
	for (int i = 1; i <= 64; ++i)
	{
		res[i][i] = 1;
	}
	while(b != 0)
	{
		if(b & 1)
			matrix_mul(res, mat);
		matrix_mul(mat, mat);
		b /= 2;
	}
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			cnt += res[i][j];
			cnt %= MOD;
		}
	}
	return cnt;
}
int main()
{
	int n;
	cin >> n;
	memset(A, 0, sizeof(A));
	map_possibilities();
	calc_matrix();
	if(n == 3)
		cout << 61;
	else
		cout << matrix_expo(A, n - 3);
}

Submission Info

Judge Result