Overview
| SHA1 Hash: | cc4202a4a6e61595a962d230f217f53bd202c5c6 |
|---|---|
| Date: | 2015-08-22 04:50:02 |
| User: | kinaba |
| Comment: | 663 |
| 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/663-U/1A.cpp version [87d196ec5b1b86d8]
> 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 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class ABBADiv1 { public: > 23 string canObtain(string initial, string target) > 24 { > 25 return can(target, initial) ? "Possible" : "Impossible"; > 26 } > 27 > 28 map<string, bool> memo; > 29 bool can(const string& X, const string& S) > 30 { > 31 if(X == S) > 32 return true; > 33 if(X.size() < S.size()) > 34 return false; > 35 if(memo.count(X)) > 36 return memo[X]; > 37 if(X[X.size()-1] == 'A' && can(X.substr(0, X.size()-1), S)) retu > 38 if(X[0] == 'B' && can(rev(X.substr(1, X.size())), S)) return mem > 39 return memo[X] = false; > 40 } > 41 > 42 string rev(const string& x) { return string(x.rbegin(), x.rend()); } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const string& Expected, const string& Received) { > 54 bool ok = (Expected == Received); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, ABBADiv1().canObtain(initial, target));} > 59 int main(){ > 60 > 61 CASE(0) > 62 string initial = "A"; > 63 string target = "BABA"; > 64 string _ = "Possible"; > 65 END > 66 CASE(1) > 67 string initial = "BAAAAABAA"; > 68 string target = "BAABAAAAAB"; > 69 string _ = "Possible"; > 70 END > 71 CASE(2) > 72 string initial = "A"; > 73 string target = "ABBA"; > 74 string _ = "Impossible"; > 75 END > 76 CASE(3) > 77 string initial = "AAABBAABB"; > 78 string target = "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"; > 79 string _ = "Possible"; > 80 END > 81 CASE(4) > 82 string initial = "AAABAAABB"; > 83 string target = "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"; > 84 string _ = "Impossible"; > 85 END > 86 /* > 87 CASE(5) > 88 string initial = ; > 89 string target = ; > 90 string _ = ; > 91 END > 92 CASE(6) > 93 string initial = ; > 94 string target = ; > 95 string _ = ; > 96 END > 97 */ > 98 } > 99 // END CUT HERE
Added SRM/663-U/1B-U.cpp version [45e1815537ebc7d2]
> 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 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned 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 = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 40 mint operator/(mint x, mint y) { return x/=y; } > 41 > 42 vector<mint> FAC_(1,1); > 43 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.siz > 44 > 45 // nCk :: O(log MODVAL) time, O(n) space. > 46 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 47 > 48 // nCk :: O(1) time, O(n^2) space. > 49 vector< vector<mint> > CP_; > 50 mint C(int n, int k) { > 51 while( CP_.size() <= n ) { > 52 int nn = CP_.size(); > 53 CP_.push_back(vector<mint>(nn+1,1)); > 54 for(int kk=1; kk<nn; ++kk) > 55 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 56 } > 57 return k<0 || n<k ? 0 : CP_[n][k]; > 58 } > 59 > 60 class ChangingChange { public: > 61 vector <int> countWays(vector <int> ways, vector <int> valueRemoved, vec > 62 { > 63 const int D = ways.size()-1; > 64 > 65 vector<mint> coins(1, 0); > 66 for(int v=1; v<=D; ++v) > 67 coins.push_back(ways[v] - eval(coins,v)); > 68 > 69 vector<int> ans; > 70 for(int q=0; q<valueRemoved.size(); ++q) { > 71 const int v=valueRemoved[q], n=numRemoved[q]; > 72 coins[v] -= n; // or += MODVAL-n, meaning mult (1+x^v)^( > 73 // then if cur is known and (1+x^v)^(MODVAL-n) is known, > 74 // O(D) to calc eval(coins,D) > 75 ans.push_back(eval(coins,D).val); > 76 coins[v] += n; > 77 } > 78 return ans; > 79 } > 80 > 81 // Calc \Pi_v (1 + x^v)^c[v] 's coeefficient at x^D > 82 // c[v] may be very large > 83 // D <= 2000 > 84 // v <= 2000 > 85 mint eval(const vector<mint>& c, int D) > 86 { > 87 vector<mint> cur(D+1, 0); > 88 cur[0] = 1; > 89 for(int v=1; v<c.size(); ++v) { > 90 cur = polymul(cur, polypow(v, c[v].val, D), D); > 91 } > 92 return D<cur.size() ? cur[D] : 0; > 93 } > 94 > 95 vector<mint> polymul(const vector<mint>& a, const vector<mint>& b, int D > 96 { > 97 int maxD = max<int>(D, (a.size()-1)*(b.size()-1)); > 98 vector<mint> c(maxD+1); > 99 for(int i=0; i<a.size(); ++i) > 100 for(int k=0; k<b.size(); ++k) > 101 if(i+k<=maxD) > 102 c[i+k] += a[i]*b[k]; > 103 return c; > 104 } > 105 vector<mint> polypow(int V, int K, int D) > 106 { > 107 vector<mint> poly; > 108 // (1+x^V)^K upto x^D > 109 mint Ckd = 1; > 110 for(int d=0; d<=K; ++d) { > 111 LL dd = LL(d)*V; > 112 if(dd > D) > 113 break; > 114 poly.resize(int(dd)+1); > 115 poly[int(dd)] = Ckd; > 116 > 117 Ckd *= (K-d); > 118 Ckd /= (d+1); > 119 } > 120 return poly; > 121 } > 122 }; > 123 > 124 // BEGIN CUT HERE > 125 #include <ctime> > 126 double start_time; string timer() > 127 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 128 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 129 { os << "{ "; > 130 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 131 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 132 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 133 bool ok = (Expected == Received); > 134 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 135 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 136 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 137 #define END verify_case(_, ChangingChange().countWays(ways, valueRemoved, n > 138 int main(){ > 139 > 140 CASE(0) > 141 int ways_[] = {1, 4, 6}; > 142 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 143 int valueRemoved_[] = {1, 1, 1}; > 144 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 145 int numRemoved_[] = {1, 2, 3}; > 146 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 147 int __[] = {3, 1, 0 }; > 148 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 149 END > 150 CASE(1) > 151 int ways_[] = {1, 2, 1, 0, 0, 0, 0, 0, 7}; > 152 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 153 int valueRemoved_[] = {8, 8, 1, 1}; > 154 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 155 int numRemoved_[] = {1, 7, 1, 2}; > 156 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 157 int __[] = {6, 0, 7, 7 }; > 158 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 159 END > 160 CASE(2) > 161 int ways_[] = {1, 2, 3, 6, 9, 14}; > 162 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 163 int valueRemoved_[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}; > 164 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 165 int numRemoved_[] = {1, 1, 1, 1, 1, 2, 2, 2, 2, 2}; > 166 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 167 int __[] = {9, 10, 11, 12, 13, 6, 8, 8, 10, 12 }; > 168 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 169 END > 170 CASE(3) > 171 int ways_[] = {1, 0}; > 172 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 173 int valueRemoved_[] = {1, 1}; > 174 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 175 int numRemoved_[] = {1, 1000000}; > 176 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 177 int __[] = {1000000006, 999000007 }; > 178 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 179 END > 180 CASE(4) > 181 int ways_[] = {1, 2, 3, 6, 9, 14}; > 182 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 183 int valueRemoved_[] = {1, 3, 5}; > 184 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 185 int numRemoved_[] = {1000000, 4, 2}; > 186 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 187 int __[] = {34955525, 2, 12 }; > 188 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 189 END > 190 /* > 191 CASE(5) > 192 int ways_[] = ; > 193 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 194 int valueRemoved_[] = ; > 195 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 196 int numRemoved_[] = ; > 197 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 198 int __[] = ; > 199 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 200 END > 201 CASE(6) > 202 int ways_[] = ; > 203 vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); > 204 int valueRemoved_[] = ; > 205 vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRem > 206 int numRemoved_[] = ; > 207 vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/s > 208 int __[] = ; > 209 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 210 END > 211 */ > 212 } > 213 // END CUT HERE
Modified lib/numeric/modArith.cpp from [c76c99fca94dfde1] to [d49aef5cfc6580a0].
25 mint operator*(mint x, mint y) { return x*=y; } 25 mint operator*(mint x, mint y) { return x*=y; } 26 26 27 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 27 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 28 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 28 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 29 mint operator/(mint x, mint y) { return x/=y; } 29 mint operator/(mint x, mint y) { return x/=y; } 30 30 31 vector<mint> FAC_(1,1); 31 vector<mint> FAC_(1,1); 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() | 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.siz 33 33 34 // nCk :: O(log MODVAL) time, O(n) space. 34 // nCk :: O(log MODVAL) time, O(n) space. 35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 36 36 37 // nCk :: O(1) time, O(n^2) space. 37 // nCk :: O(1) time, O(n^2) space. 38 vector< vector<mint> > CP_; 38 vector< vector<mint> > CP_; 39 mint C(int n, int k) { 39 mint C(int n, int k) {