fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.  /\_/\  /\_/\  /\_/\  /\_/\
  7. ( o.o )( o.o )( o.o )( o.o )
  8.  > ^ <  > ^ <  > ^ <  > ^ <
  9.  /\_/\                /\_/\
  10. ( o.o )   ghelopax   ( o.o )
  11.  > ^ <                > ^ <
  12.  /\_/\  /\_/\  /\_/\  /\_/\
  13. ( o.o )( o.o )( o.o )( o.o )
  14.  > ^ <  > ^ <  > ^ <  > ^ <
  15. */
  16.  
  17. #define ll long long
  18. #define ldb long double
  19.  
  20. const int maxN = 8;
  21. const int maxLen = 10;
  22. const int maxL = 100;
  23. const int APB = 26;
  24. const ll MOD = 998244353;
  25. const int INF = 1e9;
  26. const ll INFLL = 4e18;
  27. const int LG = 20;
  28.  
  29. #define el "\n"
  30. #define pb push_back
  31. #define eb emplace_back
  32. #define MASK(i) (1LL << (i))
  33. #define BIT(msk, i) (((msk) >> (i)) & 1LL)
  34. #define MID(l, r) ((l) + (((r) - (l)) >> 1))
  35. #define lsb(x) ((x) & -(x))
  36. #define FOR(i, l, r) for (int i = (l); i <= (int)(r); ++i)
  37. #define FORLL(i, l, r) for (ll i = (l); i <= (ll)(r); ++i)
  38. #define isz(v) (int)v.size()
  39.  
  40. void add(ll &x, ll w)
  41. {
  42.     x += w;
  43.     if (x > MOD) x -= MOD;
  44. }
  45.  
  46. int N, L;
  47. vector<string> inp;
  48.  
  49. void input()
  50. {
  51.     cin >> N >> L;
  52.  
  53.     FOR(i, 1, N)
  54.     {
  55.         string s; cin >> s;
  56.         inp.pb(s);
  57.     }
  58. }
  59.  
  60. namespace Subtask_1
  61. {
  62.     const int NodeCnt = maxN * maxLen;
  63.  
  64.     bool constraint()
  65.     {
  66.         return true;
  67.     }
  68.  
  69.     struct Trie
  70.     {
  71.         struct Node
  72.         {
  73.             int nxt[APB];
  74.             int id;
  75.         } T[NodeCnt + 5];
  76.  
  77.         Trie()
  78.         {
  79.             memset(T[0].nxt, -1, sizeof(T[0].nxt));
  80.             T[0].id = -1;
  81.         }
  82.  
  83.         int cnt = 0;
  84.  
  85.         int newnode()
  86.         {
  87.             ++cnt;
  88.             memset(T[cnt].nxt, -1, sizeof(T[cnt].nxt));
  89.             T[cnt].id = -1;
  90.             return cnt;
  91.         }
  92.  
  93.         void insert(int id, string s)
  94.         {
  95.             int u = 0;
  96.             for (char ch : s)
  97.             {
  98.                 int c = ch - 'a';
  99.  
  100.                 if (T[u].nxt[c] == -1)
  101.                     T[u].nxt[c] = newnode();
  102.  
  103.                 u = T[u].nxt[c];
  104.             }
  105.  
  106.             T[u].id = id;
  107.         }
  108.  
  109.         bool exist(int u, int c) { return T[u].nxt[c] != -1; }
  110.         int next(int u, int c) { return T[u].nxt[c]; }
  111.     };
  112.  
  113.     struct Aho_Corasick
  114.     {
  115.         Trie trie;
  116.         int fail[NodeCnt + 5];
  117.         int aut[NodeCnt + 5][APB];
  118.         int exit[NodeCnt + 5];
  119.  
  120.         void insert(int id, string s)
  121.         {
  122.             trie.insert(id, s);
  123.         }
  124.  
  125.         void build()
  126.         {
  127.             queue<int> q;
  128.  
  129.             fail[0] = 0;
  130.             exit[0] = 0;
  131.             FOR(c, 0, APB - 1)
  132.             {
  133.                 int v = trie.next(0, c);
  134.                 if (v == -1) aut[0][c] = 0;
  135.                 else
  136.                 {
  137.                     aut[0][c] = v;
  138.                     fail[v] = 0;
  139.                     exit[v] = 0;
  140.                     q.push(v);
  141.                 }
  142.             }
  143.  
  144.             while (!q.empty())
  145.             {
  146.                 int u = q.front(); q.pop();
  147.                 FOR(c, 0, APB - 1)
  148.                 {
  149.                     int v = trie.next(u, c);
  150.                     if (v == -1) aut[u][c] = aut[fail[u]][c];
  151.                     else 
  152.                     {
  153.                         fail[v] = aut[fail[u]][c];
  154.                         exit[v] = (trie.T[fail[v]].id == -1 ? exit[fail[v]] : fail[v]);
  155.                         aut[u][c] = v;
  156.                         q.push(v);
  157.                     }
  158.                 }
  159.             }
  160.         }
  161.  
  162.         vector<int> getid(int u)
  163.         {
  164.             vector<int> res;
  165.             while (u != 0)
  166.             {
  167.                 res.pb(trie.T[u].id);
  168.                 u = exit[u];
  169.             }
  170.             return res;
  171.         }
  172.     };
  173.  
  174.     struct LexicographicDP
  175.     {
  176.         Aho_Corasick ac;
  177.         ll dp[maxL + 5][NodeCnt + 5][MASK(maxN) + 5];
  178.  
  179.         void init()
  180.         {
  181.             FOR(i, 0, N - 1)
  182.                 ac.insert(i, inp[i]);
  183.  
  184.             ac.build();
  185.  
  186.             memset(dp, -1, sizeof(dp));
  187.         }
  188.  
  189.         ll count(int pos, int u, int msk)
  190.         {
  191.             ll &memo = dp[pos][u][msk];
  192.             if (memo != -1) return memo;
  193.             if (pos == L) return (msk == MASK(N) - 1);
  194.  
  195.             memo = 0;
  196.             FOR(c, 0, APB - 1)
  197.             {
  198.                 int v = ac.aut[u][c];
  199.                 vector<int> ids = ac.getid(v);
  200.                 int _msk = msk;
  201.                 if (!ids.empty()) for (int id : ids)
  202.                     _msk |= MASK(id);
  203.  
  204.                 add(memo, count(pos + 1, v, _msk));
  205.             }
  206.  
  207.             return memo;
  208.         }
  209.     } lxc;
  210.  
  211.     void preprocess()
  212.     {
  213.         lxc.init();
  214.     }
  215.  
  216.     void solve() // or: void query()
  217.     {
  218.         cout << lxc.count(0, 0, 0);
  219.     }
  220.  
  221.     void run()
  222.     {
  223.         preprocess();
  224.         solve(); // or: while(Q--) query();
  225.     }
  226. }
  227.  
  228. signed main()
  229. {
  230.     ios::sync_with_stdio(false);
  231.     cin.tie(nullptr);
  232.     cout.tie(nullptr);
  233.  
  234.     // freopen(".inp", "r", stdin);
  235.     // freopen(".out", "w", stdout);
  236.  
  237.     input();
  238.  
  239.     if (Subtask_1::constraint()) return Subtask_1::run(), 0;
  240.  
  241.     return 0;
  242. }
Success #stdin #stdout 0.02s 21808KB
comments (?)
stdin
copy 
5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj
stdout
copy 
689020583
https://ideone.com/sH7z5x
language:
C++ (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!