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

艹

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/467.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。