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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 60 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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_.size()) ); return FAC_[n]; } 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) * calcExactEulerian(k); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 88 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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.