백준3080 아름다운 이름

작성일 | In

문제 링크

  • http://icpc.me/3080

문제 출처

  • 2012/2013 COCI #3 5번

사용 알고리즘

  • Trie

풀이

트라이를 만든 뒤, (각 정점의 자식 개수)!를 곱한 것이 답입니다.
메모리 제한이 빡센데 LCP 비슷한 느낌으로 트리 압축을 해도 되고, C++의 경우 vector::shrink_to_fit를 적절히 활용해서 메모리를 줄여도 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<char, int> p;
const ll mod = 1e9+7;
ll fac[33] = {1}, ans = 1;

struct Node{
    vector<p> ch;
} nd[9090909]; int pv;

void insert(int node, const char *s){
    if(*s == 0) return;
    int idx = -1;
    for(int i=0; i<nd[node].ch.size(); i++){
        if(nd[node].ch[i].x == *s){ idx = nd[node].ch[i].y; break; }
    }
    if(idx == -1){
        nd[node].ch.emplace_back(*s, ++pv);
        nd[node].ch.shrink_to_fit();
        idx = pv;
    }
    insert(idx, s+1);
}
void dfs(int v){
    ans = ans * fac[nd[v].ch.size()] % mod;
    for(auto i : nd[v].ch) dfs(i.y);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    for(int i=1; i<33; i++) fac[i] = fac[i-1] * i % mod;
    int root = ++pv;
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        string s; cin >> s; s += '#'; insert(root, s.c_str());
    }
    dfs(root);
    cout << ans;
}