Overview
| SHA1 Hash: | af429d4fc858264dacc3370c4e3b63c455750058 |
|---|---|
| Date: | 2012-06-23 14:07:16 |
| User: | kinaba |
| Comment: | 546 |
| 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/546/1A.cpp version [a3e0995e3ee07205]
> 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 class KleofasTail { public: > 23 long long countGoodSequences(long long K, long long A, long long B) > 24 { > 25 return solve(K,B) - solve(K,A-1); > 26 } > 27 LL solve(LL K, LL U) > 28 { > 29 if(U==-1) > 30 return 0; > 31 if(K==0) > 32 return U+1; > 33 > 34 LL v = 0; > 35 for(int i=0; (K<<i)<=U; ++i) { > 36 if( (K+1<<i)-1 <= U ) > 37 v += (1LL<<i); > 38 else > 39 v += U - (K<<i) + 1; > 40 } > 41 if((K&1)==0) { > 42 ++K; > 43 for(int i=0; (K<<i)<=U; ++i) { > 44 if( (K+1<<i)-1 <= U ) > 45 v += (1LL<<i); > 46 else > 47 v += U - (K<<i) + 1; > 48 } > 49 } > 50 return v; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const long long& Expected, const long long& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, KleofasTail().countGoodSequences(K, A, B));} > 68 int main(){ > 69 CASE(0) > 70 long long K = 3LL; > 71 long long A = 4LL; > 72 long long B = 8LL; > 73 long long _ = 2LL; > 74 END > 75 CASE(1) > 76 long long K = 1LL; > 77 long long A = 23457LL; > 78 long long B = 123456LL; > 79 long long _ = 100000LL; > 80 END > 81 CASE(2) > 82 long long K = 1234567890123456LL; > 83 long long A = 10LL; > 84 long long B = 1000000LL; > 85 long long _ = 0LL; > 86 END > 87 CASE(3) > 88 long long K = 0LL; > 89 long long A = 0LL; > 90 long long B = 2LL; > 91 long long _ = 3LL; > 92 END > 93 CASE(4) > 94 long long K = 2LL; > 95 long long A = 3LL; > 96 long long B = 3LL; > 97 long long _ = 1LL; > 98 END > 99 CASE(5) > 100 long long K = 13LL; > 101 long long A = 12345LL; > 102 long long B = 67890123LL; > 103 long long _ = 8387584LL; > 104 END > 105 CASE(6) > 106 long long K = 2LL; > 107 long long A = 0LL; > 108 long long B = 6LL; > 109 long long _ = 5LL; > 110 END > 111 CASE(7) > 112 long long K = 2LL; > 113 long long A = 0LL; > 114 long long B = 9999999999999LL; > 115 long long _ = -1LL; > 116 END > 117 > 118 } > 119 // END CUT HERE
Added SRM/546/1B.cpp version [eb6666379b3e48bb]
> 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 class FavouriteDigits { public: > 23 long long findNext(long long N, int digit1, int count1, int digit2, int > 24 { > 25 LL d = 1; > 26 for(int _=0; _<15; ++_) d *= 10; > 27 > 28 LL answer = 0; > 29 > 30 bool zeros = true; > 31 for(int rest=15; d>=1; d/=10, --rest) { > 32 for(int v=0; v<=9; ++v) { > 33 int c1 = max(0, count1 - (v==digit1 && (v!=0 || > 34 int c2 = max(0, count2 - (v==digit2 && (v!=0 || > 35 bool zz = zeros && (v==0); > 36 if( rest >= c1 + c2 ) { > 37 LL cur = answer + v*d + largest(rest, di > 38 if( cur >= N ) { > 39 answer += v*d; > 40 count1 = c1; > 41 count2 = c2; > 42 zeros = zz; > 43 break; > 44 } > 45 } > 46 } > 47 } > 48 > 49 return answer; > 50 } > 51 > 52 LL largest(int rest, int d1, int c1, int d2, int c2) > 53 { > 54 if(rest==0) > 55 return 0; > 56 if(d1>d2) swap(d1,d2), swap(c1,c2); > 57 string s; > 58 for(int i=0; i<rest-c1-c2; ++i) > 59 s += '9'; > 60 for(int i=0; i<c2; ++i) > 61 s += char('0'+d2); > 62 for(int i=0; i<c1; ++i) > 63 s += char('0'+d1); > 64 stringstream sin(s); > 65 LL n; > 66 sin >> n; > 67 return n; > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const long long& Expected, const long long& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, FavouriteDigits().findNext(N, digit1, count1, di > 85 int main(){ > 86 > 87 CASE(0) > 88 long long N = 47LL; > 89 int digit1 = 1; > 90 int count1 = 0; > 91 int digit2 = 2; > 92 int count2 = 0; > 93 long long _ = 47LL; > 94 END > 95 CASE(1) > 96 long long N = 47LL; > 97 int digit1 = 5; > 98 int count1 = 0; > 99 int digit2 = 9; > 100 int count2 = 1; > 101 long long _ = 49LL; > 102 END > 103 CASE(2) > 104 long long N = 47LL; > 105 int digit1 = 5; > 106 int count1 = 0; > 107 int digit2 = 3; > 108 int count2 = 1; > 109 long long _ = 53LL; > 110 END > 111 CASE(3) > 112 long long N = 47LL; > 113 int digit1 = 2; > 114 int count1 = 1; > 115 int digit2 = 0; > 116 int count2 = 2; > 117 long long _ = 200LL; > 118 END > 119 CASE(4) > 120 long long N = 123456789012345LL; > 121 int digit1 = 1; > 122 int count1 = 2; > 123 int digit2 = 2; > 124 int count2 = 4; > 125 long long _ = 123456789012422LL; > 126 END > 127 CASE(5) > 128 long long N = 92LL; > 129 int digit1 = 1; > 130 int count1 = 1; > 131 int digit2 = 0; > 132 int count2 = 0; > 133 long long _ = 100LL; > 134 END > 135 /* > 136 CASE(6) > 137 long long N = LL; > 138 int digit1 = ; > 139 int count1 = ; > 140 int digit2 = ; > 141 int count2 = ; > 142 long long _ = LL; > 143 END > 144 */ > 145 CASE(7) > 146 long long N = 1000000000000000LL - 1; > 147 int digit1 = 5; > 148 int count1 = 5; > 149 int digit2 = 5; > 150 int count2 = 5; > 151 long long _ = -1LL; > 152 END > 153 > 154 } > 155 // END CUT HERE
Added SRM/546/1C.cpp version [246d5d9c483933cb]
> 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 = 1000000009; > 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 = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 35 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 36 mint operator+(mint x, mint y) { return x+=y; } > 37 mint operator-(mint x, mint y) { return x-=y; } > 38 mint operator*(mint x, mint y) { return x*=y; } > 39 mint operator/(mint x, mint y) { return x/=y; } > 40 vector<mint> FAC_(1,1); > 41 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 42 vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed. > 43 mint C(LL n, LL k) { > 44 while( CP_.size() <= n ) { > 45 int nn = CP_.size(); > 46 CP_.push_back(vector<mint>(nn+1,1)); > 47 for(int kk=1; kk<nn; ++kk) > 48 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 49 } > 50 return k<0 || n<k ? 0 : CP_[n][k]; > 51 } > 52 > 53 class FleaCircus { public: > 54 int countArrangements(vector <string> afterFourClicks) > 55 { > 56 stringstream sin(accumulate(afterFourClicks.begin(), afterFourCl > 57 vector<int> v; > 58 for(int n; sin>>n; ) > 59 v.push_back(n); > 60 return solve(v, v.size()); > 61 } > 62 > 63 int solve(const vector<int>& S, int N) > 64 { > 65 vector<int> cycles; > 66 { > 67 vector<bool> used(N, false); > 68 for(int s=0; s<N; ++s) > 69 if(!used[s]) { > 70 int len = 0; > 71 do { > 72 used[s] = true; > 73 s = S[s]; > 74 ++len; > 75 } while( !used[s] ); > 76 cycles.push_back(len); > 77 } > 78 } > 79 return solvesolve(cycles); > 80 } > 81 > 82 int solvesolve(const vector<int>& cycles) > 83 { > 84 map<int, int> cc; > 85 for(int i=0; i<cycles.size(); ++i) > 86 cc[cycles[i]] ++; > 87 > 88 mint total = 1; > 89 for(map<int,int>::iterator it=cc.begin(); it!=cc.end(); ++it) > 90 { > 91 int clen = it->first; > 92 int num = it->second; > 93 > 94 mint my = 0; > 95 if(clen%2 == 0) > 96 { > 97 // 4n -> n*4 > 98 if( num%4 != 0 ) > 99 return 0; > 100 my = split<4>(num) * POW(POW(clen,3)*3*2*1, num/ > 101 } > 102 else > 103 { > 104 // o -> o * 1 > 105 // 2o -> o * 2 > 106 // 4o -> o * 4 > 107 > 108 for(int fnum=0; fnum<=num; fnum+=4) > 109 for(int tnum=0; fnum+tnum<=num; tnum+=2) > 110 int onum=num-fnum-tnum; > 111 my += split<4>(fnum)*POW(POW(cle > 112 *split<2>(tnum)*POW(POW > 113 *C(num,fnum)*C(num-fnum > 114 } > 115 } > 116 total *= my; > 117 } > 118 return total.val; > 119 } > 120 > 121 template<int k> > 122 mint split(int n) > 123 { > 124 static vector<mint> memo(10000); > 125 static vector<bool> used(10000); > 126 if( n<=k ) > 127 return 1; > 128 else { > 129 if(used[n]) > 130 return memo[n]; > 131 used[n] = true; > 132 return memo[n] = C(n-1,k-1) * split<k>(n-k); > 133 } > 134 } > 135 }; > 136 > 137 // BEGIN CUT HERE > 138 #include <ctime> > 139 double start_time; string timer() > 140 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 141 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 142 { os << "{ "; > 143 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 144 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 145 void verify_case(const int& Expected, const int& Received) { > 146 bool ok = (Expected == Received); > 147 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 148 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 149 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 150 #define END verify_case(_, FleaCircus().countArrangements(afterFourClicks)) > 151 int main(){ > 152 > 153 CASE(0) > 154 string afterFourClicks_[] = {"1 2 0 3"}; > 155 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 156 int _ = 1; > 157 END > 158 CASE(1) > 159 string afterFourClicks_[] = {"1 2 ", "0 3"}; > 160 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 161 int _ = 1; > 162 END > 163 CASE(2) > 164 string afterFourClicks_[] = {"0 1 2"}; > 165 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 166 int _ = 4; > 167 END > 168 CASE(3) > 169 string afterFourClicks_[] = {"0 1 2 3 5 4"}; > 170 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 171 int _ = 0; > 172 END > 173 CASE(4) > 174 string afterFourClicks_[] = {"3 6 7 9 8 2 1", "0 5 1 0 4"}; > 175 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 176 int _ = 4; > 177 END > 178 CASE(5) > 179 string afterFourClicks_[] = {"1 0 7 5 6 3 4 2"}; > 180 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 181 int _ = 48; > 182 END > 183 /* > 184 CASE(6) > 185 string afterFourClicks_[] = ; > 186 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 187 int _ = ; > 188 END > 189 CASE(7) > 190 string afterFourClicks_[] = ; > 191 vector <string> afterFourClicks(afterFourClicks_, afterFourClicks_+siz > 192 int _ = ; > 193 END > 194 */ > 195 } > 196 // END CUT HERE