daily pastebin goal
18%
SHARE
TWEET

Untitled

a guest May 16th, 2018 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <unordered_map>
  2. #include <unordered_set>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <fstream>
  6. #include <numeric>
  7. #include <vector>
  8. #include <queue>
  9. #include <map>
  10. #include <set>
  11.  
  12. using namespace std;
  13.  
  14. ifstream in("problem5.in");
  15. ofstream out("problem5.out");
  16.  
  17.  
  18. namespace std {
  19.     template<>
  20.     struct hash<pair<int, char>>{
  21.         size_t operator()(const pair<int, char>& s) const {
  22.             return s.first + s.second;
  23.         }
  24.     };
  25.     template<>
  26.     struct hash<set<int>>{
  27.         size_t operator()(const set<int>& s) const {
  28.             //return s.empty()?0:*s.begin();
  29.             return accumulate(s.begin(), s.end(), 0, [](int a, int b){ return (a << 1) + b; });
  30.         }
  31.     };
  32. }
  33. struct compSet{
  34.     bool operator()(const set<int>& a, const set<int>& b) const {
  35.         return (*a.begin()) == (*b.begin());
  36.     }
  37. };
  38. ostream& operator<<(ostream&out, set<int> s){
  39.     for_each(s.begin(), s.end(),[&out](int i){out << i << " ";});
  40.     return out;
  41. }
  42.  
  43. struct NFA{
  44.     set<int> term;
  45.     set<int> start;
  46.     int size = 0;
  47.     unordered_map<pair<int, char>, set<int>> trans;
  48.  
  49.     NFA reverse(){
  50.         NFA r;
  51.         r.start = term;
  52.         r.term = start;
  53.         r.size = size;
  54.  
  55.         for(auto f : trans) {
  56.             int from = f.first.first;
  57.             char c = f.first.second;
  58.             for(auto to : f.second){
  59.                 r.trans[make_pair(to, c)].insert(from);
  60.             }
  61.         }
  62.         return r;
  63.     }
  64.     set<int> genericTrans(set<int> s, char c){
  65.         set<int> r;
  66.         for(auto m : s) {
  67.             auto it = trans.find(make_pair(m, c));
  68.             if(it != trans.end()){
  69.                 r.insert(it->second.begin(),it->second.end());
  70.             }
  71.         }
  72.         //cout << "GT " << s << " | " << c << " | " << r << "\n";
  73.         return r;
  74.     }
  75.     bool terminal(set<int> s){
  76.         for(auto i : s) {
  77.             if(term.count(i)) return 1;
  78.         }
  79.         return 0;
  80.     }
  81.     int cnt = 0;
  82.     unordered_map<set<int>, int> sets;
  83.     bool add(set<int> s){
  84.         if(s.empty()) return false;
  85.         if(sets.count(s)) {return false; }
  86.         sets[s] = ++cnt;
  87.         return true;
  88.     }
  89.     void process(set<int> s){
  90.         for(char c = 'a'; c <= 'z'; c++) {
  91.             set<int> reachable = genericTrans(s, c);
  92.             bool ok = add(reachable);
  93.             if(ok) process(reachable);
  94.         }
  95.     }
  96.     int transisitons() {
  97.         int ret = 0;
  98.         for (auto f : trans) {
  99.             for (auto to : f.second) {
  100.                 ret++;
  101.             }
  102.         }
  103.         return ret;
  104.     }
  105.     NFA determinize(){
  106.         NFA r;
  107.         cnt = 0;
  108.         sets.clear();
  109.         add(start);
  110.         process(start);
  111.  
  112.         for(auto from : sets) {
  113.             int fromi = from.second;
  114.             for(char c = 'a'; c <= 'z'; c++) {
  115.                 auto to = genericTrans(from.first, c);
  116.                 if(to.empty()) continue;
  117.                 int toi = sets[to];
  118.                 r.trans[make_pair(fromi, c)].insert(toi);
  119.             }
  120.         }
  121.         r.start = {sets[start]};
  122.         for(auto s : sets) {
  123.             if(terminal(s.first)) {
  124.                 r.term.insert(s.second);
  125.             }
  126.         }
  127.         r.size = sets.size();
  128.         r.target = target;
  129.         return r;
  130.     }
  131.  
  132.     set<int> delta(int s, char c){
  133.         set<int> r;
  134.         //for(auto m : s) {
  135.             auto it = trans.find(make_pair(s, c));
  136.             if(it != trans.end()){
  137.                 r.insert(it->second.begin(),it->second.end());
  138.             }
  139.         //}
  140.         return r;
  141.     }
  142.     bool terminal(int s){
  143.         //for(auto i : s) {
  144.             if (term.count(s)) return 1;
  145.         //}
  146.         return 0;
  147.     }
  148.  
  149.     int target = 0;
  150.  
  151.     #define INC(cnt) cnt = (cnt + 1) % (1000000007);
  152.     #define ADD(a, b) ((a + b) % (1000000007));
  153.  
  154.     int count() {
  155.         set<int> s = {1};
  156.         set<int> ss;
  157.         vector<uint64_t> count, count2;
  158.         count.resize(size + 1);
  159.         count2 = count;
  160.         count[1] = 1;
  161.         while(target--) {
  162.             ss.clear();
  163.             fill_n(count2.begin(), size + 1, 0);
  164.             for(auto f : s) {
  165.                 for(char c = 'a'; c <= 'z'; c++) {
  166.                     set<int> to = delta(f, c);
  167.                     for_each(to.begin(), to.end(), [&count2, &count, &ss, &f](int i){count2[i] = ADD(count2[i], count[f]); if(!ss.count(i)) ss.insert(i); });
  168.                 }
  169.             }
  170.             count = count2;
  171.             s = ss;
  172.         }
  173.  
  174.         uint64_t cnt = 0;
  175.         for(auto p : ss) {
  176.             if(terminal(p)) cnt = ADD(cnt, count[p]);
  177.         }
  178.  
  179.         return cnt;
  180.     }
  181.  
  182. };
  183.  
  184. istream& operator>>(istream&in, NFA& aut){
  185.     char c;
  186.     int n,m,k,a,b;
  187.     in >> n >> m >> k >> aut.target;
  188.     while(k--){
  189.         in >> a;
  190.         aut.term.insert(a);
  191.     }
  192.     while(m--){
  193.         in >> a >> b >> c;
  194.         aut.trans[make_pair(a, c)].insert(b);
  195.     }
  196.     aut.size = n;
  197.     aut.start.insert(1);
  198.     return in;
  199. }
  200.  
  201. ostream& operator<<(ostream&out, NFA s){
  202.     out << s.size << " " << s.trans.size() << " " << s.term.size() << endl;
  203.     out << s.term << "\n";
  204.     for (auto f : s.trans) {
  205.         for (auto to : f.second) {
  206.             out << f.first.first << " " << to << " " << f.first.second << "\n";
  207.         }
  208.     }
  209.     return out;
  210. }
  211.  
  212. ostream& xd(ostream&out, NFA s){
  213.     out << "digraph fa {" << endl;
  214.     out << "rankdir = LR;" << endl;
  215.     out << "node[shape=doublecircle];" << endl;
  216.     for(auto t : s.term) {
  217.         out << '"' << t << "\";" << endl;
  218.     }
  219.     out << "node[shape=circle];" << endl;
  220.     for (auto f : s.trans) {
  221.         for (auto to : f.second) {
  222.             out << "\"" << f.first.first << "\"->\"" << to << "\"[label=\"" << f.first.second << "\"];" << "\n";
  223.         }
  224.     }
  225.     out << "}";
  226.     return out;
  227. }
  228.  
  229. int main()
  230. {
  231.     //ifstream zin("/home/vladimir/src/lab/disc/2/I_NFA2DFA/fsa4.txt");
  232.     NFA a;
  233.     in >> a;
  234.     //TODO: We have to remove useless states first
  235.     auto b = a.determinize().count();
  236.     out << b;
  237.     //xd(out, b);
  238.     out.close();
  239.     return 0;
  240. }
RAW Paste Data
Top