Artifact 31dfe136aa2ce7ba2f84ec28e0c3ce27a97c8b71

• File SRM/541-U/1B.cpp
  • 2012-05-12 15:05:07 - part of checkin [8166493378a] on branch trunk - 541 (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>
#ifdef __GNUC__
#include <ext/hash_map>
#define unordered_map __gnu_cxx::hash_map
#else
#include <unordered_map>
#endif
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

static const int MODVAL = 1000000007;

class AkariDaisukiDiv1 { public:
	int countF(string W, string A, string D, string S, string F, int k)
	{
		string X = S;

		while(k>0 && X.size()<=F.size()) {
			X = W + X + A + X + D;
			--k;
		}

		int Usushio = naive(X, F, 0, X.size());
		if( k == 0 )
			return Usushio;

		string WW = "", DD="";
		for(int n=0,a,b,c; n<k; ++n) {
			if( n <= 50 ) {
				b = naive(X+DD+A+WW+X, F, X.size()+DD.size()-F.size()+1, X.size()+DD.size()+A.size());
				WW += W;
				DD += D;
				a = naive(WW+X, F, 0, W.size());
				c = naive(X+DD, F, X.size()+DD.size()-D.size()-F.size()+1, X.size()+DD.size());
			}
			Usushio = (Usushio*2 + a+b+c) % MODVAL;
		}
		return Usushio;
	}

	int naive(const string& X, const string& F, int S, int E)
	{
		int cnt = 0;
		for(int i=0; i+F.size()<=X.size(); ++i)
			if( S<=i && i<E )
				if( equal(X.begin()+i, X.begin()+i+F.size(), F.begin()) )
					++cnt;
		return cnt;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, AkariDaisukiDiv1().countF(Waai, Akari, Daisuki, S, F, k));}
int main(){

CASE(0)
	string Waai = "a"; 
	string Akari = "b"; 
	string Daisuki = "c"; 
	string S = "x"; 
	string F = "axb"; 
	int k = 2; 
	int _ = 2; 
END
CASE(1)
	string Waai = "a"; 
	string Akari = "b"; 
	string Daisuki = "c"; 
	string S = "x"; 
	string F = "abcdefghij"; 
	int k = 1; 
	int _ = 0; 
END
CASE(2)
	string Waai = "a"; 
	string Akari = "a"; 
	string Daisuki = "a"; 
	string S = "b"; 
	string F = "aba"; 
	int k = 2; 
	int _ = 4; 
END
CASE(3)
	string Waai = "a"; 
	string Akari = "b"; 
	string Daisuki = "c"; 
	string S = "d"; 
	string F = "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"; 
	int k = 58; 
	int _ = 191690599; 
END
CASE(4)
	string Waai = "a"; 
	string Akari = "x"; 
	string Daisuki = "y"; 
	string S = "b"; 
	string F = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; 
	int k = 49; 
	int _ = 1; 
END
CASE(5)
	string Waai = "waai"; 
	string Akari = "akari"; 
	string Daisuki = "daisuki"; 
	string S = "usushio"; 
	string F = "id"; 
	int k = 10000000; 
	int _ = 127859200; 
END
CASE(6)
	string Waai = "vfsebgjfyfgerkqlr"; 
	string Akari = "ezbiwls"; 
	string Daisuki = "kjerx"; 
	string S = "jbmjvaawoxycfndukrjfg"; 
	string F = "bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"; 
	int k = 1575724; 
	int _ = 483599313; 
END
/*
CASE(7)
	string Waai = ; 
	string Akari = ; 
	string Daisuki = ; 
	string S = ; 
	string F = ; 
	int k = ; 
	int _ = ; 
END
CASE(8)
	string Waai = ; 
	string Akari = ; 
	string Daisuki = ; 
	string S = ; 
	string F = ; 
	int k = ; 
	int _ = ; 
END
*/
}
// END CUT HERE