ADDED SRM/601-U/1A.cpp Index: SRM/601-U/1A.cpp ================================================================== --- SRM/601-U/1A.cpp +++ SRM/601-U/1A.cpp @@ -0,0 +1,111 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class WinterAndPresents { public: + long long getNumber(vector apple, vector orange) + { + const int N = apple.size(); + int Xmax = 0x3fffffff; + for(int i=0; i +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, WinterAndPresents().getNumber(apple, orange));} +int main(){ + +CASE(0) + int apple_[] = {1}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {1}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = 3LL; +END +CASE(1) + int apple_[] = {1, 2, 0, 3}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {4, 5, 0, 6}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = 0LL; +END +CASE(2) + int apple_[] = {2, 2, 2}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {2, 2, 2}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = 16LL; +END +CASE(3) + int apple_[] = {7, 4, 5}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {1, 10, 2}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = 46LL; +END +CASE(4) + int apple_[] = {1000000}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {1000000}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = 1000002000000LL; +END +CASE(5) + int apple_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = -1LL; +END +/* +CASE(6) + int apple_[] = ; + vector apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); + int orange_[] = ; + vector orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)); + long long _ = LL; +END +*/ +} +// END CUT HERE ADDED SRM/601-U/1B.cpp Index: SRM/601-U/1B.cpp ================================================================== --- SRM/601-U/1B.cpp +++ SRM/601-U/1B.cpp @@ -0,0 +1,136 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +static const unsigned MODVAL = 1000000007; +struct mint +{ + unsigned val; + mint():val(0){} + mint(int x):val(x%MODVAL) {} + mint(unsigned x):val(x%MODVAL) {} + mint(LL x):val(x%MODVAL) {} +}; +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } +mint operator+(mint x, mint y) { return x+=y; } +mint operator-(mint x, mint y) { return x-=y; } +mint operator*(mint x, mint y) { return x*=y; } + +template +struct DP3x +{ + int N1, N2, N3; + vector data; + DP3x(int, int N2, int N3, const T& t = T()) + : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<28)); } + T& operator()(int i1, int i2, int i3) + { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } + void swap(DP3x& rhs) + { data.swap(rhs.data); } +}; + +class WinterAndSnowmen { public: + int getNumber(int N, int M) + { + const int MAX = max(N,M); + mint total; + for(int B=10; B>=0; --B) + { + int HH = 2048>>(B+1); + DP3x dp(MAX+1, HH, 4); + dp(0,0,0) = 1; + for(int k=1; k<=MAX; ++k) { + for(int high=0; high>(B+1); + int kk = (k>>B)&1; + if(k<=N) + dp(k, high^kh, key^(kk<<1)) += dp(k-1,high,key); + if(k<=M) + dp(k, high^kh, key^kk) += dp(k-1,high,key); + } + } + total += dp(MAX, 0, 1); + } + return total.val; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, WinterAndSnowmen().getNumber(N, M));} +int main(){ + +CASE(0) + int N = 2; + int M = 2; + int _ = 4; +END +CASE(1) + int N = 1; + int M = 1; + int _ = 1; +END +CASE(2) + int N = 3; + int M = 5; + int _ = 74; +END +CASE(3) + int N = 7; + int M = 4; + int _ = 216; +END +CASE(4) + int N = 47; + int M = 74; + int _ = 962557390; +END +CASE(5) + int N = 2000; + int M = 2000; + int _ = -1; +END +/* +CASE(6) + int N = ; + int M = ; + int _ = ; +END +*/ +} +// END CUT HERE