fa7992ffc5 2012-08-06 kinaba: #include <iostream> fa7992ffc5 2012-08-06 kinaba: #include <sstream> fa7992ffc5 2012-08-06 kinaba: #include <iomanip> fa7992ffc5 2012-08-06 kinaba: #include <vector> fa7992ffc5 2012-08-06 kinaba: #include <string> fa7992ffc5 2012-08-06 kinaba: #include <map> fa7992ffc5 2012-08-06 kinaba: #include <set> fa7992ffc5 2012-08-06 kinaba: #include <algorithm> fa7992ffc5 2012-08-06 kinaba: #include <numeric> fa7992ffc5 2012-08-06 kinaba: #include <iterator> fa7992ffc5 2012-08-06 kinaba: #include <functional> fa7992ffc5 2012-08-06 kinaba: #include <complex> fa7992ffc5 2012-08-06 kinaba: #include <queue> fa7992ffc5 2012-08-06 kinaba: #include <stack> fa7992ffc5 2012-08-06 kinaba: #include <cmath> fa7992ffc5 2012-08-06 kinaba: #include <cassert> fa7992ffc5 2012-08-06 kinaba: using namespace std; fa7992ffc5 2012-08-06 kinaba: typedef long long LL; fa7992ffc5 2012-08-06 kinaba: typedef long double LD; fa7992ffc5 2012-08-06 kinaba: typedef complex<LD> CMP; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: static const int MODVAL = 1000000007; fa7992ffc5 2012-08-06 kinaba: struct mint fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int val; fa7992ffc5 2012-08-06 kinaba: mint():val(0){} fa7992ffc5 2012-08-06 kinaba: mint(int x):val(x%MODVAL) {} fa7992ffc5 2012-08-06 kinaba: mint(size_t x):val(x%MODVAL) {} fa7992ffc5 2012-08-06 kinaba: mint(LL x):val(x%MODVAL) {} fa7992ffc5 2012-08-06 kinaba: }; fa7992ffc5 2012-08-06 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } fa7992ffc5 2012-08-06 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } fa7992ffc5 2012-08-06 kinaba: mint operator+(mint x, mint y) { return x+=y; } fa7992ffc5 2012-08-06 kinaba: mint operator*(mint x, mint y) { return x*=y; } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: template<typename T> fa7992ffc5 2012-08-06 kinaba: vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int N = a.size(); fa7992ffc5 2012-08-06 kinaba: vector<T> u(N); fa7992ffc5 2012-08-06 kinaba: for(int i=0; i<N; ++i) fa7992ffc5 2012-08-06 kinaba: for(int j=0; j<N; ++j) fa7992ffc5 2012-08-06 kinaba: u[i] += a[i][j]*v[j]; fa7992ffc5 2012-08-06 kinaba: return u; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: template<typename T> fa7992ffc5 2012-08-06 kinaba: vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int N = a.size(); fa7992ffc5 2012-08-06 kinaba: vector< vector<T> > c(N, vector<T>(N)); fa7992ffc5 2012-08-06 kinaba: for(int i=0; i<N; ++i) fa7992ffc5 2012-08-06 kinaba: for(int j=0; j<N; ++j) fa7992ffc5 2012-08-06 kinaba: for(int k=0; k<N; ++k) fa7992ffc5 2012-08-06 kinaba: c[i][j] += a[i][k]*b[k][j]; fa7992ffc5 2012-08-06 kinaba: return c; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: template<typename T> fa7992ffc5 2012-08-06 kinaba: vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int N = a.size(); fa7992ffc5 2012-08-06 kinaba: vector< vector<T> > c(N, vector<T>(N)); fa7992ffc5 2012-08-06 kinaba: for(int i=0; i<N; ++i) c[i][i] = 1; fa7992ffc5 2012-08-06 kinaba: for(; e; e>>=1) { fa7992ffc5 2012-08-06 kinaba: if(e&1) fa7992ffc5 2012-08-06 kinaba: c = MATMUL(c, a); fa7992ffc5 2012-08-06 kinaba: a = MATMUL(a, a); fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: return c; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: class ConversionMachine { public: fa7992ffc5 2012-08-06 kinaba: int countAll(string word1, string word2, vector <int> costs, int maxCost) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int d[3] = {}; fa7992ffc5 2012-08-06 kinaba: LL minCost = 0; fa7992ffc5 2012-08-06 kinaba: for(int i=0; i<word1.size(); ++i) { fa7992ffc5 2012-08-06 kinaba: int dd=0; fa7992ffc5 2012-08-06 kinaba: while( word1[i] != word2[i] ) { fa7992ffc5 2012-08-06 kinaba: dd += 1; fa7992ffc5 2012-08-06 kinaba: minCost += costs[word1[i]-'a']; fa7992ffc5 2012-08-06 kinaba: word1[i] = (word1[i]+1-'a')%3 + 'a'; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: d[dd] += 1; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: if( minCost > maxCost ) fa7992ffc5 2012-08-06 kinaba: return 0; fa7992ffc5 2012-08-06 kinaba: LL c3 = accumulate(costs.begin(), costs.end(), 0LL); fa7992ffc5 2012-08-06 kinaba: return solve(d, (maxCost-minCost)/c3*3+d[1]*1+d[2]*2).val; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: mint solve(int d[3], int rem) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int n = d[0]+d[1]+d[2]; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: map<pair<int,int>, int> enc; fa7992ffc5 2012-08-06 kinaba: for(int b=0,id=0; b<=n; ++b) fa7992ffc5 2012-08-06 kinaba: for(int c=0; b+c<=n; ++c,++id) fa7992ffc5 2012-08-06 kinaba: enc[make_pair(b,c)] = id; fa7992ffc5 2012-08-06 kinaba: int D = enc.size(); fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: vector< vector<mint> > M(D+1, vector<mint>(D+1)); fa7992ffc5 2012-08-06 kinaba: for(int b=0; b<=n; ++b) fa7992ffc5 2012-08-06 kinaba: for(int c=0; b+c<=n; ++c) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: int a = n-b-c; fa7992ffc5 2012-08-06 kinaba: if(a) { fa7992ffc5 2012-08-06 kinaba: M[enc[make_pair(b,c+1)]][enc[make_pair(b,c)]] = a; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: if(b) { fa7992ffc5 2012-08-06 kinaba: M[enc[make_pair(b-1,c)]][enc[make_pair(b,c)]] = b; fa7992ffc5 2012-08-06 kinaba: if(b-1==0 && c==0) fa7992ffc5 2012-08-06 kinaba: M.back()[enc[make_pair(b,c)]] = b; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: if(c) { fa7992ffc5 2012-08-06 kinaba: M[enc[make_pair(b+1,c-1)]][enc[make_pair(b,c)]] = c; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: M.back().back() = 1; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: vector<mint> V(D+1); fa7992ffc5 2012-08-06 kinaba: V[enc[make_pair(d[1],d[2])]] = 1; fa7992ffc5 2012-08-06 kinaba: V.back() = V[0]; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: return MATMUL(MATPOW(M, rem), V).back(); fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: }; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: // BEGIN CUT HERE fa7992ffc5 2012-08-06 kinaba: #include <ctime> fa7992ffc5 2012-08-06 kinaba: double start_time; string timer() fa7992ffc5 2012-08-06 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fa7992ffc5 2012-08-06 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fa7992ffc5 2012-08-06 kinaba: { os << "{ "; fa7992ffc5 2012-08-06 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fa7992ffc5 2012-08-06 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fa7992ffc5 2012-08-06 kinaba: void verify_case(const int& Expected, const int& Received) { fa7992ffc5 2012-08-06 kinaba: bool ok = (Expected == Received); fa7992ffc5 2012-08-06 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fa7992ffc5 2012-08-06 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fa7992ffc5 2012-08-06 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fa7992ffc5 2012-08-06 kinaba: #define END verify_case(_, ConversionMachine().countAll(word1, word2, costs, maxCost));} fa7992ffc5 2012-08-06 kinaba: int main(){ fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: CASE(0) fa7992ffc5 2012-08-06 kinaba: string word1 = "a"; fa7992ffc5 2012-08-06 kinaba: string word2 = "b"; fa7992ffc5 2012-08-06 kinaba: int costs_[] = {100,2,3}; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = 205; fa7992ffc5 2012-08-06 kinaba: int _ = 2; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(1) fa7992ffc5 2012-08-06 kinaba: string word1 = "abcba"; fa7992ffc5 2012-08-06 kinaba: string word2 = "abcba"; fa7992ffc5 2012-08-06 kinaba: int costs_[] = {67,23,43}; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = 0; fa7992ffc5 2012-08-06 kinaba: int _ = 1; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(2) fa7992ffc5 2012-08-06 kinaba: string word1 = "cccccccc"; fa7992ffc5 2012-08-06 kinaba: string word2 = "aaaaaaaa"; fa7992ffc5 2012-08-06 kinaba: int costs_[] = {10000000,1,1}; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = 100; fa7992ffc5 2012-08-06 kinaba: int _ = 40320; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(3) fa7992ffc5 2012-08-06 kinaba: string word1 = "aa"; fa7992ffc5 2012-08-06 kinaba: string word2 = "cc"; fa7992ffc5 2012-08-06 kinaba: int costs_[] = {1,10,100}; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = 1787; fa7992ffc5 2012-08-06 kinaba: int _ = 123611681; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: /* fa7992ffc5 2012-08-06 kinaba: CASE(4) fa7992ffc5 2012-08-06 kinaba: string word1 = ; fa7992ffc5 2012-08-06 kinaba: string word2 = ; fa7992ffc5 2012-08-06 kinaba: int costs_[] = ; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = ; fa7992ffc5 2012-08-06 kinaba: int _ = ; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(5) fa7992ffc5 2012-08-06 kinaba: string word1 = ; fa7992ffc5 2012-08-06 kinaba: string word2 = ; fa7992ffc5 2012-08-06 kinaba: int costs_[] = ; fa7992ffc5 2012-08-06 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); fa7992ffc5 2012-08-06 kinaba: int maxCost = ; fa7992ffc5 2012-08-06 kinaba: int _ = ; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: */ fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: // END CUT HERE