ADDED SRM/519-U/1A.cpp
Index: SRM/519-U/1A.cpp
==================================================================
--- SRM/519-U/1A.cpp
+++ SRM/519-U/1A.cpp
@@ -0,0 +1,56 @@
+#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;
+
+class BinaryCards { public:
+ long long largestNumber(long long A_, long long B_)
+ {
+ unsigned long long A = A_;
+ unsigned long long B = B_;
+ string sa;
+ for(int i=0; (1ULL<<i)<=A; ++i)
+ sa = char('0' + ((A>>i)&1)) + sa;
+ string sb;
+ for(int i=0; (1ULL<<i)<=B; ++i)
+ sb = char('0' + ((B>>i)&1)) + sb;
+ sa = string(sb.size()-sa.size(), '0') + sa;
+
+ string sc;
+ for(int i=0; i<sb.size(); ++i)
+ if( sa[i] == sb[i] )
+ sc += sa[i];
+ else {
+ sc += string(sb.size()-i, '1');
+ break;
+ }
+
+ LL value = 0;
+ for(int i=0; i<sc.size(); ++i)
+ if( sc[sc.size()-i-1] == '1' )
+ value |= (1LL << i);
+ return value;
+ }
+};
+
+
+
+// Powered by FileEdit
+// Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom
+// Powered by CodeProcessor
ADDED SRM/519-U/1B.cpp
Index: SRM/519-U/1B.cpp
==================================================================
--- SRM/519-U/1B.cpp
+++ SRM/519-U/1B.cpp
@@ -0,0 +1,124 @@
+#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
+
ADDED lib/dataStructure/AhoCorasick.cpp
Index: lib/dataStructure/AhoCorasick.cpp
==================================================================
--- lib/dataStructure/AhoCorasick.cpp
+++ lib/dataStructure/AhoCorasick.cpp
@@ -0,0 +1,58 @@
+//-------------------------------------------------------------
+// Aho-Corasick multi pattern search
+// O(|size-of-patterns|) for construction. O(1) per step.
+//
+// Verified by
+// - SRM519 Div1 LV2
+//-------------------------------------------------------------
+
+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;
+};