Overview
| SHA1 Hash: | b247e0373a404ce2be88f969aa4e274ff63bb21a |
|---|---|
| Date: | 2015-11-18 13:37:23 |
| User: | kinaba |
| Comment: | 672 |
| 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/672-U/1A-U.cpp version [1bc022689a616900]
> 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 Procrastination { public: > 23 long long findFinalAssignee(long long n) > 24 { > 25 map<LL, set<LL>> divs; > 26 > 27 for(LL k=2; k*2<=n; ) { > 28 if(n%k==0) ++n; > 29 else if(n%k==1) --n; > 30 > 31 set<LL>& dn = divs[n]; > 32 if(dn.empty()) > 33 for(LL p=1; p*p<=n; ++p) > 34 if(n%p==0) { > 35 dn.insert(p); > 36 dn.insert(n/p); > 37 } > 38 else if((n-1)%p==0) { > 39 dn.insert(p); > 40 dn.insert((n-1)/p); > 41 } > 42 > 43 k = *dn.lower_bound(k+1); > 44 } > 45 return n; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const long long& Expected, const long long& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, Procrastination().findFinalAssignee(n));} > 63 int main(){ > 64 > 65 CASE(0) > 66 long long n = 3LL; > 67 long long _ = 3LL; > 68 END > 69 CASE(1) > 70 long long n = 8LL; > 71 long long _ = 11LL; > 72 END > 73 CASE(2) > 74 long long n = 20LL; > 75 long long _ = 20LL; > 76 END > 77 CASE(3) > 78 long long n = 196248LL; > 79 long long _ = 196259LL; > 80 END > 81 CASE(4) > 82 long long n = 5587021440LL; > 83 long long _ = 5587021440LL; > 84 END > 85 /* > 86 CASE(5) > 87 long long n = LL; > 88 long long _ = LL; > 89 END > 90 CASE(6) > 91 long long n = LL; > 92 long long _ = LL; > 93 END > 94 */ > 95 } > 96 // END CUT HERE
Added SRM/672-U/1B-U.cpp version [e145c5181a2633a0]
> 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 38 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 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()*LL(FAC_.siz > 42 > 43 // nCk :: O(1) time, O(n^2) space. > 44 vector< vector<mint> > CP_; > 45 mint C(int n, int k) { > 46 while( CP_.size() <= n ) { > 47 int nn = CP_.size(); > 48 CP_.push_back(vector<mint>(nn+1,1)); > 49 for(int kk=1; kk<nn; ++kk) > 50 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 51 } > 52 return k<0 || n<k ? 0 : CP_[n][k]; > 53 } > 54 > 55 class AlmostEulerianGraph { public: > 56 int calculateGraphs(int n) > 57 { > 58 memo.assign(n+1, -1); > 59 return (calcExactEulerian(n) * (LL(n)*(n-1)/2+1)).val; > 60 } > 61 > 62 vector<int> memo; > 63 mint calcExactEulerian(int n) > 64 { > 65 if(n == 1) > 66 return 1; > 67 if(memo[n] != -1) > 68 return memo[n]; > 69 > 70 mint sum = 0; > 71 for(int k=1; k<n; ++k) > 72 sum += k * C(n, k) * POW(2, C(n-k-1, 2).val) * calcExact > 73 return memo[n] = (POW(2, C(n-1, 2).val) - sum/n).val; > 74 } > 75 }; > 76 > 77 // BEGIN CUT HERE > 78 #include <ctime> > 79 double start_time; string timer() > 80 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 81 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 82 { os << "{ "; > 83 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 84 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 85 void verify_case(const int& Expected, const int& Received) { > 86 bool ok = (Expected == Received); > 87 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 89 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 90 #define END verify_case(_, AlmostEulerianGraph().calculateGraphs(n));} > 91 int main(){ > 92 > 93 CASE(0) > 94 int n = 3; > 95 int _ = 4; > 96 END > 97 CASE(1) > 98 int n = 2; > 99 int _ = 0; > 100 END > 101 CASE(2) > 102 int n = 42; > 103 int _ = 29010676; > 104 END > 105 CASE(3) > 106 int n = 2000; > 107 int _ = -1; > 108 END > 109 /* > 110 CASE(4) > 111 int n = ; > 112 int _ = ; > 113 END > 114 */ > 115 } > 116 // END CUT HERE