daily pastebin goal
18%
SHARE
TWEET

Untitled

a guest May 17th, 2018 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long LL;
  10.  
  11. const int MAXN = 10000;
  12. const int MAXL = 1010;
  13.  
  14. const LL MOD = (LL) 1e9 + 7;
  15.  
  16. map<char, vector<int>> steps[MAXN];
  17. map<char, int> det_steps[MAXN];
  18. bool is_term[MAXN];
  19. bool det_term[MAXN];
  20.  
  21. int cnt = 0;
  22. map<vector<int>, int> mapping;
  23. int dp[MAXL][MAXN];
  24.  
  25.  
  26. void determine(vector<int>& state) {
  27.   int u = mapping[state];
  28.   for (char c = 'a'; c <= 'z'; ++c) {
  29.     vector<int> new_state;
  30.     for (int v : state) {
  31.       new_state.insert(new_state.end(), steps[v][c].begin(), steps[v][c].end());
  32.     }
  33.  
  34.     if (new_state.size() == 0) {
  35.       continue;
  36.     }
  37.  
  38.     sort(new_state.begin(), new_state.end());
  39.     new_state.resize(unique(new_state.begin(), new_state.end()) - new_state.begin());
  40.      
  41.     if (mapping.find(new_state) == mapping.end()) {
  42.       for (int dv : new_state) {
  43.         if (is_term[dv]) {
  44.           det_term[cnt] = true;
  45.           break;
  46.         }
  47.       }
  48.       mapping[new_state] = cnt++;
  49.  
  50.       determine(new_state);
  51.     }
  52.  
  53.     det_steps[u][c] = mapping[new_state];
  54.   }
  55. }
  56.  
  57. int main() {
  58.   freopen("problem5.in", "r", stdin);
  59.   freopen("problem5.out", "w", stdout);
  60.  
  61.   int n, m, k, l;
  62.   cin >> n >> m >> k >> l;
  63.   for (int i = 0; i < k; ++i) {
  64.     int a;
  65.     cin >> a;
  66.     --a;
  67.     is_term[a] = true;
  68.   }
  69.  
  70.   for (int i = 0; i < m; ++i) {
  71.     int a, b;
  72.     char c;
  73.     cin >> a >> b >> c;
  74.     --a, --b;
  75.     steps[a][c].push_back(b);
  76.   }
  77.  
  78.   vector<int> init(1, 0);
  79.   mapping[init] = cnt++;
  80.   if (is_term[0]) {
  81.     det_term[0] = true;
  82.   }
  83.  
  84.  
  85.   determine(init);
  86.  
  87.   int sz = cnt;
  88.   for (int i = 0; i < sz; ++i) {
  89.     if (det_term[i]) {
  90.       dp[0][i] = 1;
  91.     }
  92.   }
  93.  
  94.   for (int i = 1; i <= l; ++i) {
  95.     for (int j = 0; j < sz; ++j) {
  96.       LL sum = 0;
  97.       for (pair<char, int> nxt : det_steps[j]) {
  98.         sum += dp[i - 1][nxt.second];
  99.       }
  100.       sum %= MOD;
  101.       dp[i][j] = sum;
  102.     }
  103.   }
  104.  
  105.   cout << dp[l][0] << endl;
  106.  
  107.   return 0;
  108. }
RAW Paste Data
Top