Overview
| SHA1 Hash: | 0fce7728837463aa0341f869fefccb937b9e0648 |
|---|---|
| Date: | 2015-11-18 13:37:49 |
| User: | kinaba |
| Comment: | oops |
| 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
Deleted 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 <
Name change from from SRM/672-U/1A-U.cpp to SRM/672-U/1A.cpp.
Deleted 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 <
Name change from from SRM/672-U/1B-U.cpp to SRM/672-U/1B.cpp.