a39d23ef9a 2012-12-12 kinaba: // TODO : optimize to O(n log n) a39d23ef9a 2012-12-12 kinaba: // current version looks to be running in O(n^2) ... orz a39d23ef9a 2012-12-12 kinaba: // a39d23ef9a 2012-12-12 kinaba: // TODO : clean up as a library a39d23ef9a 2012-12-12 kinaba: // a39d23ef9a 2012-12-12 kinaba: // Copy&Paste from SRM562 Div1 Hard a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: // Input is given as: a39d23ef9a 2012-12-12 kinaba: // v----c---->G[v][c] a39d23ef9a 2012-12-12 kinaba: // Must be a complete automaton. a39d23ef9a 2012-12-12 kinaba: // !!! The following code is assuming |c|==4 !!! a39d23ef9a 2012-12-12 kinaba: // a39d23ef9a 2012-12-12 kinaba: // !!! The following code is assuming the final state is {0}. a39d23ef9a 2012-12-12 kinaba: // a39d23ef9a 2012-12-12 kinaba: mint solve(vector< vector<int> >& G) a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: vector< vector<int> > set_buffer; a39d23ef9a 2012-12-12 kinaba: set<int> active_sets; a39d23ef9a 2012-12-12 kinaba: set<int> active_splitters; a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: set_buffer.push_back( vector<int>(1,0) ); a39d23ef9a 2012-12-12 kinaba: vector<int> all; a39d23ef9a 2012-12-12 kinaba: for(int v=1; v<G.size(); ++v) a39d23ef9a 2012-12-12 kinaba: all.push_back(v); a39d23ef9a 2012-12-12 kinaba: set_buffer.push_back(all); a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: active_sets.insert(0); a39d23ef9a 2012-12-12 kinaba: active_sets.insert(1); a39d23ef9a 2012-12-12 kinaba: active_splitters.insert(0); a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: while(!active_splitters.empty()) a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: const vector<int>& splv = set_buffer[*active_splitters.begin()]; a39d23ef9a 2012-12-12 kinaba: set<int> spl(splv.begin(), splv.end()); a39d23ef9a 2012-12-12 kinaba: active_splitters.erase(active_splitters.begin()); a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: for(int d=0; d<4; ++d) a39d23ef9a 2012-12-12 kinaba: for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); ) a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: int ii = *it++; a39d23ef9a 2012-12-12 kinaba: const vector<int>& cur = set_buffer[ii]; a39d23ef9a 2012-12-12 kinaba: vector<int> t, f; a39d23ef9a 2012-12-12 kinaba: for(int k=0; k<cur.size(); ++k) a39d23ef9a 2012-12-12 kinaba: (spl.count(G[cur[k]][d]) ? t : f).push_back(cur[k]); a39d23ef9a 2012-12-12 kinaba: if(!t.empty() && !f.empty()) a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: set_buffer.push_back(t); a39d23ef9a 2012-12-12 kinaba: set_buffer.push_back(f); a39d23ef9a 2012-12-12 kinaba: active_sets.insert(set_buffer.size()-2); a39d23ef9a 2012-12-12 kinaba: active_sets.insert(set_buffer.size()-1); a39d23ef9a 2012-12-12 kinaba: if(active_splitters.count(ii)) { a39d23ef9a 2012-12-12 kinaba: active_splitters.insert(set_buffer.size()-2); a39d23ef9a 2012-12-12 kinaba: active_splitters.insert(set_buffer.size()-1); a39d23ef9a 2012-12-12 kinaba: } else { a39d23ef9a 2012-12-12 kinaba: active_splitters.insert(t.size()<f.size() ? set_buffer.size()-2 : set_buffer.size()-1); a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: active_splitters.erase(ii); a39d23ef9a 2012-12-12 kinaba: active_sets.erase(ii); a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: vector<int> es; a39d23ef9a 2012-12-12 kinaba: for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); ++it) a39d23ef9a 2012-12-12 kinaba: if(*it) a39d23ef9a 2012-12-12 kinaba: es.push_back(set_buffer[*it].size()); a39d23ef9a 2012-12-12 kinaba: /* a39d23ef9a 2012-12-12 kinaba: for(bool changed=true; changed;) a39d23ef9a 2012-12-12 kinaba: { a39d23ef9a 2012-12-12 kinaba: changed=false; a39d23ef9a 2012-12-12 kinaba: for(int i=0; i<eqs.size(); ++i) if(!eqs[i].second && !dead[i]){ a39d23ef9a 2012-12-12 kinaba: set<int> spl(eqs[i].first.begin(), eqs[i].first.end()); a39d23ef9a 2012-12-12 kinaba: eqs[i].second = true; a39d23ef9a 2012-12-12 kinaba: for(int k=0; k<eqs.size(); ++k) a39d23ef9a 2012-12-12 kinaba: for(int d=0; d<4; ++d) if(!dead[k]) { a39d23ef9a 2012-12-12 kinaba: vector<int> t, f; a39d23ef9a 2012-12-12 kinaba: for(vector<int>::iterator it=eqs[k].first.begin(); it!=eqs[k].first.end(); ++it) a39d23ef9a 2012-12-12 kinaba: (spl.count(G[*it][d]) ? t : f).push_back(*it); a39d23ef9a 2012-12-12 kinaba: if(!t.empty() && !f.empty()) { a39d23ef9a 2012-12-12 kinaba: if(eqs[k].second) { a39d23ef9a 2012-12-12 kinaba: eqs.push_back(make_pair(t,t.size()>f.size())); a39d23ef9a 2012-12-12 kinaba: eqs.push_back(make_pair(f,t.size()<=f.size())); a39d23ef9a 2012-12-12 kinaba: dead.push_back(false); a39d23ef9a 2012-12-12 kinaba: dead.push_back(false); a39d23ef9a 2012-12-12 kinaba: changed = true; a39d23ef9a 2012-12-12 kinaba: } else { a39d23ef9a 2012-12-12 kinaba: eqs.push_back(make_pair(t,false)); a39d23ef9a 2012-12-12 kinaba: eqs.push_back(make_pair(f,false)); a39d23ef9a 2012-12-12 kinaba: dead.push_back(false); a39d23ef9a 2012-12-12 kinaba: dead.push_back(false); a39d23ef9a 2012-12-12 kinaba: changed = true; a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: dead[k] = true; a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: a39d23ef9a 2012-12-12 kinaba: vector<int> es; a39d23ef9a 2012-12-12 kinaba: for(int i=1; i<eqs.size(); ++i) if(!dead[i]) a39d23ef9a 2012-12-12 kinaba: es.push_back(eqs[i].first.size()); a39d23ef9a 2012-12-12 kinaba: */ a39d23ef9a 2012-12-12 kinaba: int sum = accumulate(es.begin(), es.end(), 0); a39d23ef9a 2012-12-12 kinaba: mint x = POW(2, sum); a39d23ef9a 2012-12-12 kinaba: for(int i=0; i<es.size(); ++i) a39d23ef9a 2012-12-12 kinaba: x -= POW(2, es[i])-1; a39d23ef9a 2012-12-12 kinaba: return x-1; a39d23ef9a 2012-12-12 kinaba: } a39d23ef9a 2012-12-12 kinaba: