8166493378 2012-05-12 kinaba: #include <iostream> 8166493378 2012-05-12 kinaba: #include <sstream> 8166493378 2012-05-12 kinaba: #include <iomanip> 8166493378 2012-05-12 kinaba: #include <vector> 8166493378 2012-05-12 kinaba: #include <string> 8166493378 2012-05-12 kinaba: #include <map> 8166493378 2012-05-12 kinaba: #include <set> 8166493378 2012-05-12 kinaba: #include <algorithm> 8166493378 2012-05-12 kinaba: #include <numeric> 8166493378 2012-05-12 kinaba: #include <iterator> 8166493378 2012-05-12 kinaba: #include <functional> 8166493378 2012-05-12 kinaba: #include <complex> 8166493378 2012-05-12 kinaba: #include <queue> 8166493378 2012-05-12 kinaba: #include <stack> 8166493378 2012-05-12 kinaba: #include <cmath> 8166493378 2012-05-12 kinaba: #include <cassert> 8166493378 2012-05-12 kinaba: #include <cstring> 8166493378 2012-05-12 kinaba: #ifdef __GNUC__ 8166493378 2012-05-12 kinaba: #include <ext/hash_map> 8166493378 2012-05-12 kinaba: #define unordered_map __gnu_cxx::hash_map 8166493378 2012-05-12 kinaba: #else 8166493378 2012-05-12 kinaba: #include <unordered_map> 8166493378 2012-05-12 kinaba: #endif 8166493378 2012-05-12 kinaba: using namespace std; 8166493378 2012-05-12 kinaba: typedef long long LL; 8166493378 2012-05-12 kinaba: typedef complex<double> CMP; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: static const int MODVAL = 1000000007; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: class AkariDaisukiDiv1 { public: 8166493378 2012-05-12 kinaba: int countF(string W, string A, string D, string S, string F, int k) 8166493378 2012-05-12 kinaba: { 8166493378 2012-05-12 kinaba: string X = S; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: while(k>0 && X.size()<=F.size()) { 8166493378 2012-05-12 kinaba: X = W + X + A + X + D; 8166493378 2012-05-12 kinaba: --k; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: int Usushio = naive(X, F, 0, X.size()); 8166493378 2012-05-12 kinaba: if( k == 0 ) 8166493378 2012-05-12 kinaba: return Usushio; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: string WW = "", DD=""; 8166493378 2012-05-12 kinaba: for(int n=0,a,b,c; n<k; ++n) { 8166493378 2012-05-12 kinaba: if( n <= 50 ) { 8166493378 2012-05-12 kinaba: b = naive(X+DD+A+WW+X, F, X.size()+DD.size()-F.size()+1, X.size()+DD.size()+A.size()); 8166493378 2012-05-12 kinaba: WW += W; 8166493378 2012-05-12 kinaba: DD += D; 8166493378 2012-05-12 kinaba: a = naive(WW+X, F, 0, W.size()); 8166493378 2012-05-12 kinaba: c = naive(X+DD, F, X.size()+DD.size()-D.size()-F.size()+1, X.size()+DD.size()); 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: Usushio = (Usushio*2 + a+b+c) % MODVAL; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: return Usushio; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: int naive(const string& X, const string& F, int S, int E) 8166493378 2012-05-12 kinaba: { 8166493378 2012-05-12 kinaba: int cnt = 0; 8166493378 2012-05-12 kinaba: for(int i=0; i+F.size()<=X.size(); ++i) 8166493378 2012-05-12 kinaba: if( S<=i && i<E ) 8166493378 2012-05-12 kinaba: if( equal(X.begin()+i, X.begin()+i+F.size(), F.begin()) ) 8166493378 2012-05-12 kinaba: ++cnt; 8166493378 2012-05-12 kinaba: return cnt; 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: }; 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: // BEGIN CUT HERE 8166493378 2012-05-12 kinaba: #include <ctime> 8166493378 2012-05-12 kinaba: double start_time; string timer() 8166493378 2012-05-12 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 8166493378 2012-05-12 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 8166493378 2012-05-12 kinaba: { os << "{ "; 8166493378 2012-05-12 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 8166493378 2012-05-12 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 8166493378 2012-05-12 kinaba: void verify_case(const int& Expected, const int& Received) { 8166493378 2012-05-12 kinaba: bool ok = (Expected == Received); 8166493378 2012-05-12 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 8166493378 2012-05-12 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 8166493378 2012-05-12 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 8166493378 2012-05-12 kinaba: #define END verify_case(_, AkariDaisukiDiv1().countF(Waai, Akari, Daisuki, S, F, k));} 8166493378 2012-05-12 kinaba: int main(){ 8166493378 2012-05-12 kinaba: 8166493378 2012-05-12 kinaba: CASE(0) 8166493378 2012-05-12 kinaba: string Waai = "a"; 8166493378 2012-05-12 kinaba: string Akari = "b"; 8166493378 2012-05-12 kinaba: string Daisuki = "c"; 8166493378 2012-05-12 kinaba: string S = "x"; 8166493378 2012-05-12 kinaba: string F = "axb"; 8166493378 2012-05-12 kinaba: int k = 2; 8166493378 2012-05-12 kinaba: int _ = 2; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(1) 8166493378 2012-05-12 kinaba: string Waai = "a"; 8166493378 2012-05-12 kinaba: string Akari = "b"; 8166493378 2012-05-12 kinaba: string Daisuki = "c"; 8166493378 2012-05-12 kinaba: string S = "x"; 8166493378 2012-05-12 kinaba: string F = "abcdefghij"; 8166493378 2012-05-12 kinaba: int k = 1; 8166493378 2012-05-12 kinaba: int _ = 0; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(2) 8166493378 2012-05-12 kinaba: string Waai = "a"; 8166493378 2012-05-12 kinaba: string Akari = "a"; 8166493378 2012-05-12 kinaba: string Daisuki = "a"; 8166493378 2012-05-12 kinaba: string S = "b"; 8166493378 2012-05-12 kinaba: string F = "aba"; 8166493378 2012-05-12 kinaba: int k = 2; 8166493378 2012-05-12 kinaba: int _ = 4; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(3) 8166493378 2012-05-12 kinaba: string Waai = "a"; 8166493378 2012-05-12 kinaba: string Akari = "b"; 8166493378 2012-05-12 kinaba: string Daisuki = "c"; 8166493378 2012-05-12 kinaba: string S = "d"; 8166493378 2012-05-12 kinaba: string F = "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"; 8166493378 2012-05-12 kinaba: int k = 58; 8166493378 2012-05-12 kinaba: int _ = 191690599; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(4) 8166493378 2012-05-12 kinaba: string Waai = "a"; 8166493378 2012-05-12 kinaba: string Akari = "x"; 8166493378 2012-05-12 kinaba: string Daisuki = "y"; 8166493378 2012-05-12 kinaba: string S = "b"; 8166493378 2012-05-12 kinaba: string F = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; 8166493378 2012-05-12 kinaba: int k = 49; 8166493378 2012-05-12 kinaba: int _ = 1; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(5) 8166493378 2012-05-12 kinaba: string Waai = "waai"; 8166493378 2012-05-12 kinaba: string Akari = "akari"; 8166493378 2012-05-12 kinaba: string Daisuki = "daisuki"; 8166493378 2012-05-12 kinaba: string S = "usushio"; 8166493378 2012-05-12 kinaba: string F = "id"; 8166493378 2012-05-12 kinaba: int k = 10000000; 8166493378 2012-05-12 kinaba: int _ = 127859200; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(6) 8166493378 2012-05-12 kinaba: string Waai = "vfsebgjfyfgerkqlr"; 8166493378 2012-05-12 kinaba: string Akari = "ezbiwls"; 8166493378 2012-05-12 kinaba: string Daisuki = "kjerx"; 8166493378 2012-05-12 kinaba: string S = "jbmjvaawoxycfndukrjfg"; 8166493378 2012-05-12 kinaba: string F = "bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"; 8166493378 2012-05-12 kinaba: int k = 1575724; 8166493378 2012-05-12 kinaba: int _ = 483599313; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: /* 8166493378 2012-05-12 kinaba: CASE(7) 8166493378 2012-05-12 kinaba: string Waai = ; 8166493378 2012-05-12 kinaba: string Akari = ; 8166493378 2012-05-12 kinaba: string Daisuki = ; 8166493378 2012-05-12 kinaba: string S = ; 8166493378 2012-05-12 kinaba: string F = ; 8166493378 2012-05-12 kinaba: int k = ; 8166493378 2012-05-12 kinaba: int _ = ; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: CASE(8) 8166493378 2012-05-12 kinaba: string Waai = ; 8166493378 2012-05-12 kinaba: string Akari = ; 8166493378 2012-05-12 kinaba: string Daisuki = ; 8166493378 2012-05-12 kinaba: string S = ; 8166493378 2012-05-12 kinaba: string F = ; 8166493378 2012-05-12 kinaba: int k = ; 8166493378 2012-05-12 kinaba: int _ = ; 8166493378 2012-05-12 kinaba: END 8166493378 2012-05-12 kinaba: */ 8166493378 2012-05-12 kinaba: } 8166493378 2012-05-12 kinaba: // END CUT HERE