Overview
| SHA1 Hash: | f94ac98860837390201e737894fb64e795a74de9 |
|---|---|
| Date: | 2016-12-29 13:33:57 |
| User: | kinaba |
| Comment: | 704. A tabun atteru. |
| 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/704-U/1A.cpp version [3950e09c2280ab10]
> 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 TreeDistanceConstruction { public: > 23 vector <int> construct(vector <int> d) > 24 { > 25 map<int, vector<int>> d2i; > 26 for (int i = 0; i < d.size(); ++i) > 27 d2i[d[i]].push_back(i); > 28 > 29 const int m = d2i.begin()->first; > 30 const int M = d2i.rbegin()->first; > 31 vector<int> ans; > 32 > 33 if (d2i[m].size() >= 3) > 34 return vector<int>(); > 35 > 36 int L = d2i[m].front(), R = d2i[m].back(); > 37 if (d2i[m].size() == 1) { > 38 if (2 * m != M) > 39 return vector<int>(); > 40 } > 41 else { // d2i[m].size() == 2 > 42 if (2*m-1 != M) > 43 return vector<int>(); > 44 ans.push_back(L); > 45 ans.push_back(R); > 46 } > 47 > 48 for (int k = m + 1; k <= M; ++k) { > 49 if (d2i[k].size() < 2) > 50 return vector<int>(); > 51 for (int i = 0; i < d2i[k].size(); ++i) { > 52 ans.push_back(i == 0 ? L : R); > 53 ans.push_back(d2i[k][i]); > 54 } > 55 L = d2i[k].front(); > 56 R = d2i[k].back(); > 57 } > 58 return ans; > 59 } > 60 }; > 61 > 62 // BEGIN CUT HERE > 63 #include <ctime> > 64 double start_time; string timer() > 65 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 66 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 67 { os << "{ "; > 68 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 69 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 70 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 71 bool ok = (Expected == Received); > 72 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 73 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 74 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 75 #define END verify_case(_, TreeDistanceConstruction().construct(d));} > 76 int main(){ > 77 > 78 CASE(0) > 79 int d_[] = {3,2,2,3}; > 80 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 81 int __[] = {1, 2, 1, 0, 2, 3 }; > 82 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 83 END > 84 CASE(1) > 85 int d_[] = {1,2,2,2}; > 86 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 87 int __[] = {0, 1, 0, 2, 0, 3 }; > 88 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 89 END > 90 CASE(2) > 91 int d_[] = {1,1,1,1}; > 92 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 93 vector <int> _; > 94 END > 95 CASE(3) > 96 int d_[] = {1,1,1}; > 97 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 98 vector <int> _; > 99 END > 100 CASE(4) > 101 int d_[] = {1,1}; > 102 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 103 int __[] = {0, 1 }; > 104 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(5) > 107 int d_[] = { 2,2,3,3,3 }; > 108 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 109 int __[] = { -1 }; > 110 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 111 END > 112 CASE(6) > 113 int d_[] = { 3,4,4,5,6,6 }; > 114 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 115 int __[] = { -1 }; > 116 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 } > 119 // END CUT HERE
Added SRM/704-U/1B-U.cpp version [3f49b98f321c4503]
> 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 *= > 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 LL eulerPhi(LL n) { > 43 LL ans = n; > 44 for (LL x = 2; x*x <= n; ++x) { > 45 if (n % x == 0) { > 46 ans -= ans / x; > 47 while (n % x == 0) n /= x; > 48 } > 49 } > 50 if (n > 1) ans -= ans / n; > 51 return ans; > 52 } > 53 > 54 class ModEquation { public: > 55 vector <int> count(int n, int K, vector <int> query) > 56 { > 57 int epk = (int)eulerPhi(K); > 58 > 59 vector<pair<int, int>> dK; > 60 int v = K; > 61 for (int p = 2; p*p <= v; ++p) > 62 if (v%p == 0) { > 63 int cnt = 0; > 64 while (v%p == 0) cnt++, v /= p; > 65 dK.emplace_back(p, cnt); > 66 } > 67 if (v != 1) > 68 dK.emplace_back(v, 1); > 69 > 70 vector<int> ans; > 71 for (int q : query) > 72 ans.push_back(solve(n, K, epk, dK, q).val); > 73 return ans; > 74 } > 75 > 76 // # of solutions in mod K world s.t. x[0] x[1] ... x[n-1] = q > 77 // > 78 // * n <= 50 > 79 // * K = BIG > 80 // * must be solved 1000 times in time limits. > 81 mint solve(int n, int K, int epk, const vector<pair<int,int>>& dK, int q > 82 { > 83 if (n == 1) > 84 return 1; > 85 > 86 mint ans = POW(epk, n-1); > 87 > 88 for (auto pe : dK) { > 89 int p = pe.first; > 90 int e = pe.second; > 91 int qq = q; > 92 int cnt = 0; > 93 while (qq%p == 0 && cnt<e) > 94 cnt++, qq /= p; > 95 // p^cnt is in gcd(K,q) > 96 if (cnt < e) { > 97 ans *= POW(n, cnt); // div dups... > 98 } > 99 else { > 100 ans *= POW(n, cnt); // or more... > 101 } > 102 } > 103 > 104 return ans; > 105 } > 106 }; > 107 > 108 // BEGIN CUT HERE > 109 #include <ctime> > 110 double start_time; string timer() > 111 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 112 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 113 { os << "{ "; > 114 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 115 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 116 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 117 bool ok = (Expected == Received); > 118 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 119 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 120 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 121 #define END verify_case(_, ModEquation().count(n, K, query));} > 122 int main(){ > 123 > 124 CASE(0) > 125 int n = 2; > 126 int K = 2; > 127 int query_[] = {0,1}; > 128 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 129 int __[] = {3, 1 }; > 130 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 131 END > 132 CASE(1) > 133 int n = 2; > 134 int K = 4; > 135 int query_[] = {0,1,2,3}; > 136 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 137 int __[] = {8, 2, 4, 2 }; > 138 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 139 END > 140 CASE(2) > 141 int n = 6; > 142 int K = 6; > 143 int query_[] = {4}; > 144 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 145 int __[] = {2016 }; > 146 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 147 END > 148 CASE(3) > 149 int n = 1; > 150 int K = 2; > 151 int query_[] = {0,0,0,1,1,1}; > 152 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 153 int __[] = {1, 1, 1, 1, 1, 1 }; > 154 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 155 END > 156 /* > 157 CASE(4) > 158 int n = ; > 159 int K = ; > 160 int query_[] = ; > 161 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 162 int __[] = ; > 163 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 164 END > 165 CASE(5) > 166 int n = ; > 167 int K = ; > 168 int query_[] = ; > 169 vector <int> query(query_, query_+sizeof(query_)/sizeof(*query_)); > 170 int __[] = ; > 171 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 172 END > 173 */ > 174 } > 175 // END CUT HERE