d82ca3d4de 2014-05-29 kinaba: #include <iostream> d82ca3d4de 2014-05-29 kinaba: #include <sstream> d82ca3d4de 2014-05-29 kinaba: #include <iomanip> d82ca3d4de 2014-05-29 kinaba: #include <vector> d82ca3d4de 2014-05-29 kinaba: #include <string> d82ca3d4de 2014-05-29 kinaba: #include <map> d82ca3d4de 2014-05-29 kinaba: #include <set> d82ca3d4de 2014-05-29 kinaba: #include <algorithm> d82ca3d4de 2014-05-29 kinaba: #include <numeric> d82ca3d4de 2014-05-29 kinaba: #include <iterator> d82ca3d4de 2014-05-29 kinaba: #include <functional> d82ca3d4de 2014-05-29 kinaba: #include <complex> d82ca3d4de 2014-05-29 kinaba: #include <queue> d82ca3d4de 2014-05-29 kinaba: #include <stack> d82ca3d4de 2014-05-29 kinaba: #include <cmath> d82ca3d4de 2014-05-29 kinaba: #include <cassert> d82ca3d4de 2014-05-29 kinaba: #include <tuple> d82ca3d4de 2014-05-29 kinaba: using namespace std; d82ca3d4de 2014-05-29 kinaba: typedef long long LL; d82ca3d4de 2014-05-29 kinaba: typedef complex<double> CMP; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: struct SaComp { d82ca3d4de 2014-05-29 kinaba: const int sp, *sr, srlen; d82ca3d4de 2014-05-29 kinaba: SaComp(int sp, const vector<int>& sr) : sp(sp), sr(&sr[0]), srlen(sr.size()) {} d82ca3d4de 2014-05-29 kinaba: bool operator()(int a, int b) const d82ca3d4de 2014-05-29 kinaba: { return make_pair(sr[a], a+sp<srlen?sr[a+sp]:0x7fffffff) d82ca3d4de 2014-05-29 kinaba: < make_pair(sr[b], b+sp<srlen?sr[b+sp]:0x7fffffff); } d82ca3d4de 2014-05-29 kinaba: }; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: template<typename RanIt> d82ca3d4de 2014-05-29 kinaba: vector<int> compute_suffix_array(RanIt beg, RanIt end) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: const int N = end - beg; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: vector<int> sa(N); d82ca3d4de 2014-05-29 kinaba: vector<int> sort_rank(beg, end); d82ca3d4de 2014-05-29 kinaba: for(int i=0; i<N; ++i) d82ca3d4de 2014-05-29 kinaba: sa[i] = i; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: sort(sa.begin(), sa.end(), SaComp(0, sort_rank)); d82ca3d4de 2014-05-29 kinaba: for(int sorted_prefix=1; sorted_prefix<N; sorted_prefix*=2) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: SaComp cmp(sorted_prefix, sort_rank); d82ca3d4de 2014-05-29 kinaba: sort(sa.begin(), sa.end(), cmp); d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: vector<int> block_id(N); d82ca3d4de 2014-05-29 kinaba: for(int i=1; i<N; ++i) d82ca3d4de 2014-05-29 kinaba: block_id[i] = block_id[i-1] + (cmp(sa[i-1], sa[i]) ? 1 : 0); d82ca3d4de 2014-05-29 kinaba: for(int i=0; i<N; ++i) d82ca3d4de 2014-05-29 kinaba: sort_rank[sa[i]] = block_id[i]; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: return sa; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: vector<int> inv_sa(const vector<int>& sa) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: vector<int> isa(sa.size()); d82ca3d4de 2014-05-29 kinaba: for(int i=0; i<sa.size(); ++i) d82ca3d4de 2014-05-29 kinaba: isa[sa[i]] = i; d82ca3d4de 2014-05-29 kinaba: return isa; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: template<typename RanIte> d82ca3d4de 2014-05-29 kinaba: vector<int> longest_common_prefix(RanIte beg, RanIte end, const vector<int>& sa) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: const int N = sa.size(); d82ca3d4de 2014-05-29 kinaba: vector<int> lcp(N); d82ca3d4de 2014-05-29 kinaba: vector<int> inv = inv_sa(sa); d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: int len = 0; d82ca3d4de 2014-05-29 kinaba: for(int i=0; i<N; ++i) { d82ca3d4de 2014-05-29 kinaba: int sa_idx = inv[i]; d82ca3d4de 2014-05-29 kinaba: if( sa_idx == 0 ) d82ca3d4de 2014-05-29 kinaba: lcp[sa_idx] = -1; d82ca3d4de 2014-05-29 kinaba: else { d82ca3d4de 2014-05-29 kinaba: for(int k=sa[sa_idx-1]; i+len<N && k+len<N && *(beg+i+len)==*(beg+k+len);) d82ca3d4de 2014-05-29 kinaba: ++len; d82ca3d4de 2014-05-29 kinaba: lcp[sa_idx] = len; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: if(len) --len; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: return lcp; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: class StringsNightmareAgain { public: d82ca3d4de 2014-05-29 kinaba: long long UniqueSubstrings(int a, int b, int c, int d, int n) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: string S(n,'a'); d82ca3d4de 2014-05-29 kinaba: for(int i=0; i<a; ++i) { d82ca3d4de 2014-05-29 kinaba: b = int((LL(b)*c+d)%n); d82ca3d4de 2014-05-29 kinaba: S[b] = 'b'; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: return solve(S); d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: LL solve(const string& S) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: vector<int> sa = compute_suffix_array(S.begin(), S.end()); d82ca3d4de 2014-05-29 kinaba: vector<int> lcp = longest_common_prefix(S.begin(), S.end(), sa); d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: for(int i=0; i+1<sa.size(); ++i) d82ca3d4de 2014-05-29 kinaba: { d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: return 0; d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: }; d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: // BEGIN CUT HERE d82ca3d4de 2014-05-29 kinaba: #include <ctime> d82ca3d4de 2014-05-29 kinaba: double start_time; string timer() d82ca3d4de 2014-05-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d82ca3d4de 2014-05-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d82ca3d4de 2014-05-29 kinaba: { os << "{ "; d82ca3d4de 2014-05-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d82ca3d4de 2014-05-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d82ca3d4de 2014-05-29 kinaba: void verify_case(const long long& Expected, const long long& Received) { d82ca3d4de 2014-05-29 kinaba: bool ok = (Expected == Received); d82ca3d4de 2014-05-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d82ca3d4de 2014-05-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d82ca3d4de 2014-05-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d82ca3d4de 2014-05-29 kinaba: #define END verify_case(_, StringsNightmareAgain().UniqueSubstrings(a, b, c, d, n));} d82ca3d4de 2014-05-29 kinaba: int main(){ d82ca3d4de 2014-05-29 kinaba: d82ca3d4de 2014-05-29 kinaba: CASE(0) d82ca3d4de 2014-05-29 kinaba: int a = 0; d82ca3d4de 2014-05-29 kinaba: int b = 0; d82ca3d4de 2014-05-29 kinaba: int c = 0; d82ca3d4de 2014-05-29 kinaba: int d = 0; d82ca3d4de 2014-05-29 kinaba: int n = 4; d82ca3d4de 2014-05-29 kinaba: long long _ = 2LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(1) d82ca3d4de 2014-05-29 kinaba: int a = 2; d82ca3d4de 2014-05-29 kinaba: int b = 3; d82ca3d4de 2014-05-29 kinaba: int c = 1; d82ca3d4de 2014-05-29 kinaba: int d = 1; d82ca3d4de 2014-05-29 kinaba: int n = 6; d82ca3d4de 2014-05-29 kinaba: long long _ = 3LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(2) d82ca3d4de 2014-05-29 kinaba: int a = 4; d82ca3d4de 2014-05-29 kinaba: int b = 3; d82ca3d4de 2014-05-29 kinaba: int c = 1; d82ca3d4de 2014-05-29 kinaba: int d = 1; d82ca3d4de 2014-05-29 kinaba: int n = 6; d82ca3d4de 2014-05-29 kinaba: long long _ = 3LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(3) d82ca3d4de 2014-05-29 kinaba: int a = 4; d82ca3d4de 2014-05-29 kinaba: int b = 3; d82ca3d4de 2014-05-29 kinaba: int c = 3; d82ca3d4de 2014-05-29 kinaba: int d = 3; d82ca3d4de 2014-05-29 kinaba: int n = 10; d82ca3d4de 2014-05-29 kinaba: long long _ = 5LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(4) d82ca3d4de 2014-05-29 kinaba: int a = 5; d82ca3d4de 2014-05-29 kinaba: int b = 3; d82ca3d4de 2014-05-29 kinaba: int c = 2; d82ca3d4de 2014-05-29 kinaba: int d = 3; d82ca3d4de 2014-05-29 kinaba: int n = 11; d82ca3d4de 2014-05-29 kinaba: long long _ = 9LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(5) d82ca3d4de 2014-05-29 kinaba: int a = 10; d82ca3d4de 2014-05-29 kinaba: int b = 1000000; d82ca3d4de 2014-05-29 kinaba: int c = 1000000; d82ca3d4de 2014-05-29 kinaba: int d = 1; d82ca3d4de 2014-05-29 kinaba: int n = 51; d82ca3d4de 2014-05-29 kinaba: long long _ = 63LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: /* d82ca3d4de 2014-05-29 kinaba: CASE(6) d82ca3d4de 2014-05-29 kinaba: int a = ; d82ca3d4de 2014-05-29 kinaba: int b = ; d82ca3d4de 2014-05-29 kinaba: int c = ; d82ca3d4de 2014-05-29 kinaba: int d = ; d82ca3d4de 2014-05-29 kinaba: int n = ; d82ca3d4de 2014-05-29 kinaba: long long _ = LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: CASE(7) d82ca3d4de 2014-05-29 kinaba: int a = ; d82ca3d4de 2014-05-29 kinaba: int b = ; d82ca3d4de 2014-05-29 kinaba: int c = ; d82ca3d4de 2014-05-29 kinaba: int d = ; d82ca3d4de 2014-05-29 kinaba: int n = ; d82ca3d4de 2014-05-29 kinaba: long long _ = LL; d82ca3d4de 2014-05-29 kinaba: END d82ca3d4de 2014-05-29 kinaba: */ d82ca3d4de 2014-05-29 kinaba: } d82ca3d4de 2014-05-29 kinaba: // END CUT HERE