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 国际许可协议 进行许可。
您可以自由地转载,但请务必注明文章来源且不可用于商业目的。