Overview
| SHA1 Hash: | c81888b8095e61fb9f40f809aebef91afdb8ac2c |
|---|---|
| Date: | 2012-08-06 15:25:10 |
| User: | kinaba |
| Comment: | 550 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/550-U/1C.cpp version [b366e6f6edd62cdd]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 static const int MODVAL = 1000000007; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(size_t x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 33 mint operator+(mint x, mint y) { return x+=y; } > 34 mint operator*(mint x, mint y) { return x*=y; } > 35 > 36 template<typename T> > 37 vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) > 38 { > 39 int N = a.size(); > 40 vector<T> u(N); > 41 for(int i=0; i<N; ++i) > 42 for(int j=0; j<N; ++j) > 43 u[i] += a[i][j]*v[j]; > 44 return u; > 45 } > 46 > 47 template<typename T> > 48 vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> > 49 { > 50 int N = a.size(); > 51 vector< vector<T> > c(N, vector<T>(N)); > 52 for(int i=0; i<N; ++i) > 53 for(int j=0; j<N; ++j) > 54 for(int k=0; k<N; ++k) > 55 c[i][j] += a[i][k]*b[k][j]; > 56 return c; > 57 } > 58 > 59 template<typename T> > 60 vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) > 61 { > 62 int N = a.size(); > 63 vector< vector<T> > c(N, vector<T>(N)); > 64 for(int i=0; i<N; ++i) c[i][i] = 1; > 65 for(; e; e>>=1) { > 66 if(e&1) > 67 c = MATMUL(c, a); > 68 a = MATMUL(a, a); > 69 } > 70 return c; > 71 } > 72 > 73 class ConversionMachine { public: > 74 int countAll(string word1, string word2, vector <int> costs, int maxCost > 75 { > 76 int d[3] = {}; > 77 LL minCost = 0; > 78 for(int i=0; i<word1.size(); ++i) { > 79 int dd=0; > 80 while( word1[i] != word2[i] ) { > 81 dd += 1; > 82 minCost += costs[word1[i]-'a']; > 83 word1[i] = (word1[i]+1-'a')%3 + 'a'; > 84 } > 85 d[dd] += 1; > 86 } > 87 > 88 if( minCost > maxCost ) > 89 return 0; > 90 LL c3 = accumulate(costs.begin(), costs.end(), 0LL); > 91 return solve(d, (maxCost-minCost)/c3*3+d[1]*1+d[2]*2).val; > 92 } > 93 > 94 mint solve(int d[3], int rem) > 95 { > 96 int n = d[0]+d[1]+d[2]; > 97 > 98 map<pair<int,int>, int> enc; > 99 for(int b=0,id=0; b<=n; ++b) > 100 for(int c=0; b+c<=n; ++c,++id) > 101 enc[make_pair(b,c)] = id; > 102 int D = enc.size(); > 103 > 104 vector< vector<mint> > M(D+1, vector<mint>(D+1)); > 105 for(int b=0; b<=n; ++b) > 106 for(int c=0; b+c<=n; ++c) > 107 { > 108 int a = n-b-c; > 109 if(a) { > 110 M[enc[make_pair(b,c+1)]][enc[make_pair(b,c)]] = > 111 } > 112 if(b) { > 113 M[enc[make_pair(b-1,c)]][enc[make_pair(b,c)]] = > 114 if(b-1==0 && c==0) > 115 M.back()[enc[make_pair(b,c)]] = b; > 116 } > 117 if(c) { > 118 M[enc[make_pair(b+1,c-1)]][enc[make_pair(b,c)]] > 119 } > 120 } > 121 M.back().back() = 1; > 122 > 123 vector<mint> V(D+1); > 124 V[enc[make_pair(d[1],d[2])]] = 1; > 125 V.back() = V[0]; > 126 > 127 return MATMUL(MATPOW(M, rem), V).back(); > 128 } > 129 }; > 130 > 131 // BEGIN CUT HERE > 132 #include <ctime> > 133 double start_time; string timer() > 134 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 135 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 136 { os << "{ "; > 137 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 138 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 139 void verify_case(const int& Expected, const int& Received) { > 140 bool ok = (Expected == Received); > 141 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 142 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 143 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 144 #define END verify_case(_, ConversionMachine().countAll(word1, word2, costs > 145 int main(){ > 146 > 147 CASE(0) > 148 string word1 = "a"; > 149 string word2 = "b"; > 150 int costs_[] = {100,2,3}; > 151 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 152 int maxCost = 205; > 153 int _ = 2; > 154 END > 155 CASE(1) > 156 string word1 = "abcba"; > 157 string word2 = "abcba"; > 158 int costs_[] = {67,23,43}; > 159 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 160 int maxCost = 0; > 161 int _ = 1; > 162 END > 163 CASE(2) > 164 string word1 = "cccccccc"; > 165 string word2 = "aaaaaaaa"; > 166 int costs_[] = {10000000,1,1}; > 167 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 168 int maxCost = 100; > 169 int _ = 40320; > 170 END > 171 CASE(3) > 172 string word1 = "aa"; > 173 string word2 = "cc"; > 174 int costs_[] = {1,10,100}; > 175 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 176 int maxCost = 1787; > 177 int _ = 123611681; > 178 END > 179 /* > 180 CASE(4) > 181 string word1 = ; > 182 string word2 = ; > 183 int costs_[] = ; > 184 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 185 int maxCost = ; > 186 int _ = ; > 187 END > 188 CASE(5) > 189 string word1 = ; > 190 string word2 = ; > 191 int costs_[] = ; > 192 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 193 int maxCost = ; > 194 int _ = ; > 195 END > 196 */ > 197 } > 198 // END CUT HERE
Modified lib/numeric/modArith.cpp from [e5662c451b84a185] to [4e73ce5907de5c44].
34 int nn = CP_.size(); 34 int nn = CP_.size(); 35 CP_.push_back(vector<mint>(nn+1,1)); 35 CP_.push_back(vector<mint>(nn+1,1)); 36 for(int kk=1; kk<nn; ++kk) 36 for(int kk=1; kk<nn; ++kk) 37 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 37 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 38 } 38 } 39 return k<0 || n<k ? 0 : CP_[n][k]; 39 return k<0 || n<k ? 0 : CP_[n][k]; 40 } 40 } > 41 > 42 template<typename T> > 43 vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) > 44 { > 45 int N = a.size(); > 46 vector<T> u(N); > 47 for(int i=0; i<N; ++i) > 48 for(int j=0; j<N; ++j) > 49 u[i] += a[i][j]*v[j]; > 50 return u; > 51 } > 52 > 53 template<typename T> > 54 vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> > 55 { > 56 int N = a.size(); > 57 vector< vector<T> > c(N, vector<T>(N)); > 58 for(int i=0; i<N; ++i) > 59 for(int j=0; j<N; ++j) > 60 for(int k=0; k<N; ++k) > 61 c[i][j] += a[i][k]*b[k][j]; > 62 return c; > 63 } > 64 > 65 template<typename T> > 66 vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) > 67 { > 68 int N = a.size(); > 69 vector< vector<T> > c(N, vector<T>(N)); > 70 for(int i=0; i<N; ++i) c[i][i] = 1; > 71 for(; e; e>>=1) { > 72 if(e&1) > 73 c = MATMUL(c, a); > 74 a = MATMUL(a, a); > 75 } > 76 return c; > 77 } 41 78 42 /* 79 /* 43 // MODVAL must be a prime!! 80 // MODVAL must be a prime!! 44 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 81 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 45 { 82 { 46 if( b > e ) return 0; 83 if( b > e ) return 0; 47 if( k <= 1 ) return k*(e-b+1); 84 if( k <= 1 ) return k*(e-b+1); 48 return DIV(SUB(POW(k, e+1), POW(k,b)), k-1); 85 return DIV(SUB(POW(k, e+1), POW(k,b)), k-1); 49 } 86 } 50 87 51 LL Cpascal(LL n, LL k) < 52 { < 53 vector< vector<LL> > c(n+1, vector<LL>(k+1)); < 54 for(LL nn=1; nn<=n; ++nn) < 55 for(LL kk=0; kk<=min(nn,k); ++kk) < 56 c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[n < 57 return c[n][k]; < 58 } < 59 < 60 vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b) < 61 { < 62 int N = a.size(); < 63 vector< vector<LL> > c(N, vector<LL>(N)); < 64 for(int i=0; i<N; ++i) < 65 for(int j=0; j<N; ++j) < 66 for(int k=0; k<N; ++k) < 67 c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j])); < 68 return c; < 69 } < 70 < 71 // works for non-prime MODVAL 88 // works for non-prime MODVAL 72 LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1 89 LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1 73 { 90 { 74 vector< vector<LL> > v(2, vector<LL>(2)); 91 vector< vector<LL> > v(2, vector<LL>(2)); 75 vector< vector<LL> > x(2, vector<LL>(2)); 92 vector< vector<LL> > x(2, vector<LL>(2)); 76 v[0][0] = v[1][1] = 1; 93 v[0][0] = v[1][1] = 1; 77 x[0][0] = x_; x[0][1] = 0; 94 x[0][0] = x_; x[0][1] = 0;