[BOJ] 1616 드럼통 메시지

https://www.acmicpc.net/problem/1616

1616번: 드럼통 메시지

일단 길이가 \(M-1\) 개로 이루어진 모든 메시지에 대해 다음 메시지로 나올 수 있는 메시지들에 대해 간선을 이어준다.

이때, 간선의 가중치에는 추가되는 수가 부여된다.

아래의 경우는 \(K = 2\), \(M = 3\) 인 경우다.

\(K = 2\), \(M = 3\)인 경우에 대한 그래프다.

여기서 오일러 경로를 사용해 지나쳐온 모든 간선들의 가중치를 저장해둔다.

지나는 간선의 방문 시각을 빨간색 수로 표시해두었다.

저장된 값은 \(11101000\)이고, 놀랍게도, 저장된 메시지는 우리가 찾고자 하는 답이 된다.

시간 복잡도는 \(O(K^{M-1}*K)\) = \(O(K^{M})\) 이 된다.

직접 간선을 만들면 MLE가 나기 때문에 간선을 만들지 않고 처리해야 한다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18+10;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,k,ne,pw = 1,p = -1,pv[4200005];

void dfs(int x) {
    while(pv[x] != n) {
        ne = 1LL*x*n%pw+pv[x];
        pv[x]++;
        dfs(ne);
    }
    if(p != -1) cout << p << ' ';
    p = x%n;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    if(k-- == 1) {
        for(int i = 0;i < n;i++) cout << i << ' ';
        return 0;
    }
    for(int i = 1;i <= k;i++) pw *= n;
    dfs(0);
}