HDU – 2825 Wireless Password AC自动机+状压dp

ProLightsfx 2017-5-18 120 5/18

Wireless Password AC自动机+状压dp

Source

HDU - 2825

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

- THE END -

ProLightsfx

11月15日14:21

最后修改:2024年11月15日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论