길 잃은 HYSBZ - 1297dp 매트릭스 최적화

문제풀이
구한 시간 t가 너무 커서 직접 밀어내는 방식을 사용할 수 없기 때문에 매트릭스 스피드 幂를 사용하여 택배 밀어내는 속도의 복잡도를 O(n*10)^3logt)로 낮추어 d[code(i,j)]로 i초 전 j노드의 방안수를 표시하고 최대 10초를 저장한다. 코드는 인코딩 함수로 전이 매트릭스tran을 정의한다.매번 이동 행렬을 곱할 때마다 현재 시간을 1초 뒤로 미루기 때문에tran[code(i, j)] [code(i+1.j)]=1은 각 노드가 현재 시간에서 다음 초로 이동하는 시간을 표시하고, i는 시간 j는 노드 번호가 제목에 주어진 변(i, j, c)은 i절에서 j 노드로 가는 데 c초가 걸리면tran[code(c-1, i)] [code(0, j)]=1은 c초 전에 현재 시간으로 이동하는 것을 의미하며, -1은 매번 곱할 때마다 이동 행렬을 1초 뒤로 미루기 때문이다.
AC 코드

#include 
#include 
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 110;
const int MOD = 2009;

struct Matrix
{
	ll m[MAXN][MAXN];
	static const int N = 100; //  
	Matrix(int v = 0)
	{
		memset(m, 0, sizeof(m));
		if (v)
			for (int i = 0; i < N; i++)
				m[i][i] = v;
	}
	Matrix operator * (const Matrix &b)
	{
		Matrix t;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					t.m[i][j] = (t.m[i][j] + m[i][k] * b.m[k][j]) % MOD;
		return t;
	}
	friend Matrix operator ^ (Matrix a, int n)
	{
		Matrix t(1);
		while (n)
		{
			if (n & 1)
				t = t * a;
			a = a * a;
			n >>= 1;
		}
		return t;
	}
}tran, a; //a[0][code(i, j)]  i  j           10 
int code(int t, int x) //  t x  
{
	return t * 10 + x;
}
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	int n, t;
	cin >> n >> t;
	for (int i = 0; i < n; i++)
	{
		char c;
		for (int j = 0; j < n; j++)
		{
			scanf(" %c", &c);
			c -= '0';
			if (c)
				tran.m[code(c - 1, i)][code(0, j)] = 1; //c   i   0     j -1       1   
		}
	}
	a.m[0][0] = 1; //   1
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < n; j++)
			tran.m[code(i, j)][code(i + 1, j)] = 1; //            1     
	a = a * (tran ^ t);
	cout << a.m[0][n - 1] << endl;

	return 0;
}