BOJ 18457 Knowledge

문제 링크입니다.

문제 요약

a 와 b로만 이루어진 문자열의 임의의 위치에 다음의 6가지 연산

• aa 를 추가/제거
• bbb 를 추가/제거
• ababab 를 추가/제거

을 원하는 만큼 적용해 만들 수 있는 서로 다른 길이 $K$의 문자열의 수를 구하세요.

풀이

위의 연산만을 적용해 얻을 수 있는 문자열들을 같은 상태로 취급합시다.

빈 문자열에서 출발해 문자열 뒤에 a나 b를 붙여 문자열을 만들어낸다고 생각하면, 어떤 문자를 붙일 때마다 상태의 전이가 일어날 것이고, 이를 인접 행렬로 만들 수 있다면 (그리고 상태 수가 충분히 작다면) 문제를 쉽게 해결할 수 있습니다.

b 를 세 번 연속으로 붙이거나, a를 두 번 연속으로 붙이면 원래 자리로 돌아온다는 사실을 확인할 수 있습니다. a를 쓰는 건 양방향 간선처럼 취급할 수 있고, b를 쓰는 건 삼각형 사이클을 만들어 줍니다. 이 삼각형들을 a의 양방향 간선으로 서로 이어주는 형태로 상태 전이 그래프를 그릴 수 있을 겁니다. 일단 가장 기본이 되는 사이클로부터 아래와 같이 12개의 상태를 가진 그래프를 그려볼 수 있습니다.

이제 여기서 중복되는 상태를 제거하고 겉의 6개 상태에 a 간선을 어떻게 연결해야 하는 지, 새로운 사이클이 필요한지 확인해야 합니다. 그리고 놀랍게도, 각 상태 뒤에 a 를 붙인 뒤 ababab 를 적당히 추가하고 aa 나 bbb 를 연속해서 제거하는 방식으로 동치인 상태를 찾으면, 위의 12가지 상태가 끝임을 알 수 있습니다!

따라서 문제를 ${\cal O}(N+12^3 \lg K)$에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using mat = vector<vector<ll>>;
const ll mod = 998244353;

mat operator* (const mat& a, const mat& b){
	mat c(12, vector<ll>(12));
	
	for (int i = 0; i < 12; i++)
		for (int j = 0; j < 12; j++){
			for (int k = 0; k < 12; k++)
				c[i][j] += a[i][k] * b[k][j];

			c[i][j] %= mod;
		}
	return c;
}

mat operator*= (mat& a, mat& b){return a = a*b;}

mat pw(mat a, ll r){
	mat ret(12, vector<ll>(12));
	for(int i = 0; i < 12; i++) ret[i][i] = 1;
	while(r){
		if(r&1) ret = ret*a;
		a = a*a;
		r >>= 1;
	}
	return ret;
}

mat adj(12);
vector<int> a, b;

void init(){
	for(int i = 0; i < 12; i++) adj[i].resize(12);
	adj[0][1] = adj[1][2] = adj[2][0] = 1;
	adj[3][4] = adj[4][5] = adj[5][3] = 1;
	adj[6][7] = adj[7][8] = adj[8][6] = 1;
	adj[9][10] = adj[10][11] = adj[11][9] = 1;
	adj[0][3] = adj[3][0] = 1; adj[1][6] = adj[6][1] = 1; adj[2][9] = adj[9][2] = 1;
	adj[4][11] = adj[11][4] = 1; adj[5][7] = adj[7][5] = 1; adj[8][10] = adj[10][8] = 1;
	a = {3,6,9,0,11,7,1,5,10,2,8,4};
	b = {1,2,0,4,5,3,7,8,6,10,11,9};
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	init();
	int n; string s; ll k; cin >> n >> s >> k;
	int goal = 0; for(auto& c : s){
		if(c == 'a') goal = a[goal];
		else goal = b[goal];
	}
	cout << pw(adj, k)[0][goal];
}