Problem A PFS集合

题面

一个由若干字符串构成,且不存在一个字符串是另一个字符串的前缀的集合是PFS集合。特别的$\emptyset$也是PFS集合。

例如$\{"hello"\}$和$\{"hello", "goodbye", "giant", "hi"\}$是PFS集合,但$\{"hello","hell"\}$和$\{"great","gig","g"}$不是。

现有一集合,试求其是PFS集合的子集个数对$9191$取模后的值。

题解

Trie树,树上统计。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int N, tot;
char s[55];
int trie[1100001][27];
int value[1100001];
void Insert() {
    int u = 0;
    int len = strlen( s + 1 );
    for ( int i = 1; i <= len; ++i ) {
        int c = s[i] - 'a' + 1;
        if ( !trie[u][c] )
            trie[u][c] = ++tot;
        u = trie[u][c];
    }
    value[u] = 1;
}
int dfs( int u=0 ) {
    int sum = 1;
    for ( int i = 1; i <= 26; ++i )
        if ( trie[u][i] ) {
            int k = dfs( trie[u][i] );
            sum *= k;
            sum %= 9191;
        }
    value[u] += sum;
    value[u] %= 9191;
    return value[u];
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    while(n--){
        cin>>s+1;
        Insert();
    }
    cout<<dfs()%9191<<endl;
    return 0;
}

Problem B

Last modification:September 30, 2019
如果您觉得我的文章有用,给颗糖糖吧~