Artifact 148e8147aebc92eb9137c46674a57c65aaa2d03e

• File SRM/519-U/1B.cpp
  • 2011-09-20 15:23:58 - part of checkin [96b8b260e1] on branch trunk - 519 (user: kinaba) [annotate]
• File SRM/519/1B.cpp
  • 2011-09-21 09:12:45 - part of checkin [28a087506a] on branch trunk - 519 (user: kinaba) [annotate]

#include <iostream> 
#include <sstream> 
#include <iomanip> 
#include <vector> 
#include <string> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <numeric> 
#include <iterator> 
#include <functional> 
#include <complex> 
#include <queue> 
#include <stack> 
#include <cmath> 
#include <cassert> 
#include <cstring> 
using namespace std; 
typedef long long LL; 
typedef complex<double> CMP; 

template<int NC=26, char BC='a'>
struct AhoCorasick
{
	AhoCorasick( const vector<string>& p ) : link(NC+1) {
		// Create a trie
		for(int i=0; i<p.size(); ++i) {
			AhoCorasick* t = this;
			for(int k=0; k<p[i].size(); t=t->link[p[i][k++]-BC])
				if(!t->link[p[i][k]-BC])
					t->link[p[i][k]-BC]=new AhoCorasick;
			t->final.insert(i);
		}

		// Do BFS and draw failure links, and prepare for substring pattern
		queue<AhoCorasick*> Q;
		for(int c=0; c<NC; ++c)
			if( link[c] ) {
				Q.push(link[c]);
				link[c]->link[NC] = this; // "c"'s suffix is ""
				link[c]->final.insert(final.begin(), final.end());
			}
			else
				link[c] = this;
		while( !Q.empty() ) {
			AhoCorasick* t=Q.front(); Q.pop();
			for(int c=0; c<NC; ++c)
				if( t->link[c] ) {
					Q.push(t->link[c]);
					AhoCorasick* r = t->link[NC]; // "r" is suffix of "t"...
					while( !r->link[c] )
						r = r->link[NC];
					t->link[c]->link[NC] = r->link[c]; // then "rc" is suffix of "tc"
					t->link[c]->final.insert(r->link[c]->final.begin(), r->link[c]->final.end());
				}
		}
	}
	const AhoCorasick* start() const { return this; }
	const AhoCorasick* next(char c) const {
		const AhoCorasick* t = this;
		while( !t->link[c-BC] )
			t = t->link[NC];
		return t->link[c-BC];
	}
	const set<int>& accept() const { return final; }
	~AhoCorasick() { for(int i=0; i<NC; ++i) if(link[i]!=this) delete link[i]; }
private:
	AhoCorasick() : link(NC+1) {}
	vector<AhoCorasick*> link;
	set<int> final;
};

static const int MODVAL = 1000000009; // must be prime for op/ 
struct mint 
{ 
  int val; 
  mint():val(0){}
  mint(int x):val(x%MODVAL) {}
}; 
mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 

int bitcnt(LL x)
{
	int c = 0;
	for(; x; x>>=1)
		c += x&1;
	return c;
}

class RequiredSubstrings { public: 
  int solve(vector <string> words, int C, int L) 
  { 
    AhoCorasick<> ac(words); 
    return rec(L, C, 0, ac.start()).val;
  } 

  map<pair<pair<int,int>,const AhoCorasick<>*>, mint> memo; 
  mint rec(int rest, const int C, const int found, const AhoCorasick<>* ac) 
  { 
    if( rest == 0 )
      return (bitcnt(found)==C ? 1 : 0); 
    pair<pair<int,int>,const AhoCorasick*> key(make_pair(rest, found), ac); 
    if( memo.count(key) ) 
      return memo[key]; 

    mint sum = 0; 
    for(char c='a'; c<='z'; ++c) 
    { 
      const AhoCorasick<>* t = ac->next(c); 
      int f = found;
      for(set<int>::const_iterator it=t->accept().begin(); it!=t->accept().end(); ++it) 
        f |= (1 << *it);
      sum += rec(rest-1, C, f, t);  
    } 
    return memo[key] = sum; 
  } 
}; 



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom
// Powered by CodeProcessor