Wireless Password AC自动机+状压dp
Source
My Solution
题意:给出一个字符串集合,集合里包含m(m <= 10)个长度不大于10的字符串,要求构造长度为n(1<=n<=25)的字符串且子串中至少出现k个集合里的字符串,求方案数 MOD 20090717。
AC自动机+状压dp
AC自动机上统计类的dp问题,dpijs表示在处理主串第i个字符遍历到了AC自动机上的j号节点s且当前构造成的字符串中包含的集合信息s时的方案数。
这里的s是一个长度为10的二进制数(表现形式为32位的带符号),第i位为1则表示构造出的字符串中包含了给定集合中的第i个字符串。
若dpijs != 0, dp[i+1][j][s | danger[ch[j][k]] += dp[i][j][s];
然后危险节点记录当前以此节点为字符串结束节点的字符串集合(同样是一个长度为10的二进制数)。
然后对s里包含至少k个集合中的字符串的dp[n][j][s]求和。
复杂度 O(T*n*ac.sz*(1<<10)*CHAR_SIZE)
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int MOD = 20090717;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 1e2 + 8;
inline int mp(char ch){
return ch - 'a';
}
inline int mod(int x)
{
return x - x / MOD * MOD;
}
struct AC_Machine{
int ch[MAX_SIZE][CHAR_SIZE], danger[MAX_SIZE], fail[MAX_SIZE];
int sz;
void init(){
sz = 1;
memset(ch[0], 0, sizeof ch[0]);
memset(danger, 0, sizeof danger);
}
void _insert(const string &s, int m){
int n = s.size();
int u = 0, c;
for(int i = 0; i < n; i++){
c = mp(s[i]);
if(!ch[u][c]){
memset(ch[sz], 0, sizeof ch[sz]);
danger[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
danger[u] |= 1 << m;
}
void _build(){
queue Q;
fail[0] = 0;
for(int c = 0, u; c < CHAR_SIZE; c++){
u = ch[0][c];
if(u){Q.push(u); fail[u] = 0;}
}
int r;
while(!Q.empty()){
r = Q.front();
Q.pop();
danger[r] |= danger[fail[r]];
for(int c = 0, u; c < CHAR_SIZE; c++){
u = ch[r][c];
if(!u){ch[r][c] = ch[fail[r]][c]; continue; }
fail[u] = ch[fail[r]][c];
Q.push(u);
}
}
}
}ac;
string ss;
int dp[2][MAX_SIZE][1<<10]; inline bool check(int x, int k) { int t, cnt = 0; while(x){ if(x&1) cnt++; x >>= 1;
}
if(cnt >= k) return true;
else return false;
}
int main()
{
#ifdef LOCAL
freopen("26.in", "r", stdin);
//freopen("26.out", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false); cin.tie(0);
int n, m, kk, len, i, j, k, s, x, u;
int ans;
while(true){
cin >> n >> m >> kk;
if(n == 0 && m == 0 && kk == 0) break;
ac.init();
for(i = 0; i < m; i++){ cin >> ss;
//cout << ss << endl;
ac._insert(ss, i);
}
ac._build();
memset(dp, 0, sizeof dp);
dp[0][0][0] = 1;
for(i = 0, x = 1; i < n; i++, x ^= 1){
memset(dp[x], 0, sizeof dp[x]);
for(j = 0; j < ac.sz; j++){
for(s = 0; s < (1<<m); s++){
if(dp[x^1][j][s] == 0) continue;
for(k = 0; k < CHAR_SIZE; k++){
u = ac.ch[j][k];//cout << i << " " << j << " " << k << endl;
dp[x][u][s|ac.danger[u]] = mod(dp[x][u][s|ac.danger[u]] + dp[x^1][j][s]);
}
}
}
}
ans = 0;
for(s = 0; s < (1<<m); s++){
if(!check(s, kk)) continue;
for(j = 0; j < ac.sz; j++){
ans = mod(ans + dp[x^1][j][s]);
}
}
cout << ans << "n";
}
return 0;
}
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/hdu-2825-wireless-password-ac-machine/
共有 0 条评论