BZOJ 4861 魔法咒语

\(BZOJ 1009 dp\)方面的弱化版，加大了矩阵构造难度和预处理难度

题面：https://www.lydsy.com/JudgeOnline/problem.php?id=4861

Solution：

对于\(L\leq 100\)的正常在\(dfa\)上跑\(dp\)即可，需要预处理点\(p\)接上串\(i\)以后在\(trie\)

图上匹配到了哪个点，以及中间有没有禁点(能否转移)

定义\(matchNode[p][k]\)为点\(p\)匹配完串\(k\)以后的位置，

\(nxter[p][k]\)为是否能转移。

显然可以得到：
\[ nxtA = f[i + len[k]][matchNode[p][k]] + f[i][p]; \]
\[ f[i + len[k]][matchNode[p][k]] = nxtA; \]

考虑后面\(L\leq 10^9\)的数据，转移范围\(\leq2\)显然是矩阵快速幂。

对于初始矩阵\(ss\)，第一行上放\(f[1]\)以及\(f[2]\)，

对于转移矩阵\(G\)，分成四个部分，左上为\(0\)，右上为距离为\(2\)的转移，

左下为单位矩阵，右下为距离为\(1\)的转移

注意如果\(dfa\)及建立从\(0\)开始，那么对应节点数应该\(+1\)，并且匹配到的点在矩阵上也\(+1\)

就是\(dfa\)向矩阵映射\(+1\)，反过来映射\(-1\)。

#include<cctype>
#include<cstdio>
#include<cstring>
const int N = 3e3+7;
typedef long long LL;
inline int max(int a, int b) {return a > b ? a : b;}
inline int min(int a, int b) {return a > b ? b : a;}

const int MOD = 1e9+7;
int pcnt = 0; int n, m, L;
struct Trie {   
  int fail, son[26], fa, end;
}t[N];
int totstr = 0, len[N];char str[60][60];
inline void ins(char *ss) {
  int lens = strlen(ss + 1), p = 0; 
  for (int i = 1; i <= lens; i++) {
    if (!t[p].son[ss[i] - 'a']) t[p].son[ss[i] - 'a'] = ++pcnt;
    p = t[p].son[ss[i] - 'a'];
  } t[p].end |= 1;
}
#include<queue>
int nxter[N][60], matchNode[N][60];
inline void getfail() {
  std :: queue<int> q;
  for (int i = 0; i < 26; i++) if (t[0].son[i])
    q.push(t[0].son[i]), t[t[0].son[i]].fail = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 0; i < 26; i++) if (t[u].son[i])
      t[t[u].son[i]].fail = t[t[u].fail].son[i], q.push(t[u].son[i]);
    else t[u].son[i] = t[t[u].fail].son[i];
    t[u].end |= t[t[u].fail].end; 
  } 
  for (int i = 0; i <= pcnt; i++) for (int j = 1; j <= totstr; j++) {
    int p = i;
    if (t[i].end) nxter[i][j] |= 1;
    else {
      int flag = 0;
      for (int k = 1; k <= len[j]; k++) {
        p = t[p].son[str[j][k] - 'a'];
        if (t[p].end) {
          nxter[i][j] |= 1, flag |= 1; break;
        }
      } if (!flag) matchNode[i][j] = p;
    }
  }
}
LL f[107][N];//f[i][j]表示填到第i位,在j节点
inline void dp(){
  f[0][0] = 1;
  for (int i = 0; i <= L; i++) for (int p = 0; p <= pcnt; p++) {
    if (t[p].end) continue;
    for (int k = 1; k <= totstr; k++) {
      if (i + len[k] <= L && !nxter[p][k]) {
        int nxtA = f[i + len[k]][matchNode[p][k]] + f[i][p];
        nxtA >= MOD ? nxtA -= MOD : 0;
        f[i + len[k]][matchNode[p][k]] = nxtA;
      }
    }
  }
}
char sin[N]; int upmax = 203;
struct Mat {
  LL A[203][203];
  inline void clean() {memset(A, 0, sizeof(A));}
  inline void mem1() {
    for (int i = 1; i <= upmax; i++) A[i][i] = 1;
  }
};
inline Mat Mul(Mat A, Mat B) {
  Mat C; C.clean(); 
  for (int i = 1; i <= upmax; i++) for (int j = 1; j <= upmax; j++)
    for (int k = 1; k <= upmax; k++) {
      C.A[i][j] = (C.A[i][j] + A.A[i][k] * B.A[k][j]) % MOD;
    } return C;
}
inline Mat FST(Mat A, int k) {
  Mat C; C.clean(); C.mem1();
  while (k) {
    if (k & 1) C = Mul(C, A); A = Mul(A, A), k >>= 1;
  } return C;
}
Mat G, unit;
void MatIN() {
  upmax = pcnt + 1, G.clean();
  for (int i = 1; i <= upmax; i++) G.A[i + upmax][i] = 1;
  for (int i = 1; i <= upmax; i++) {
    for (int j = 1; j <= n; j++) if (!nxter[i - 1][j] && !t[i - 1].end) {
      if (len[j] == 2) G.A[i][matchNode[i - 1][j] + 1 + upmax]++;
      if (len[j] == 1) G.A[i + upmax][matchNode[i - 1][j] + 1 + upmax]++;
    }
  }
  f[0][0] = 1;
  for (int i = 0; i <= 3; i++) for (int p = 0; p <= pcnt; p++) {
    if (t[p].end) continue;
    for (int k = 1; k <= totstr; k++) {
      if (i + len[k] <= L && !nxter[p][k]) {
        int nxtA = f[i + len[k]][matchNode[p][k]] + f[i][p];
        nxtA >= MOD ? nxtA -= MOD : 0;
        f[i + len[k]][matchNode[p][k]] = nxtA;
      }
    }
  }
  unit.clean(); 
  for (int i = 1; i <= upmax; i++) 
    unit.A[1][i] = f[1][i - 1], unit.A[1][i + upmax] = f[2][i - 1];
}
void init() {
  scanf ("%d%d%d", &n, &m, &L);
  for (int i = 1; i <= n; i++) 
    scanf ("%s", str[i] + 1), len[i] = strlen(str[i] + 1);
  totstr = n;
  for (int i = 1; i <= m; i++) scanf ("%s", sin + 1), ins(sin);
}
int main() {
  init(), getfail();
  if (L <= 100) {
    dp(); LL ans = 0;
    for (int i = 0; i <= pcnt; i++) ans = (ans + f[L][i]) % MOD;
    printf ("%lld", ans);
  } else {
    MatIN(), upmax *= 2, G = FST(G, L - 1), unit = Mul(unit, G);
    LL ans = 0;
    for (int i = 1; i <= pcnt; i++) ans = (ans + unit.A[1][i]) % MOD;
    printf ("%lld", ans);
  }
return 0;
}

BZOJ 4861 魔法咒语

原文：https://www.cnblogs.com/cjc030205/p/11638107.html