14e544f8d9 2011-09-28 kinaba: #include <iostream> 14e544f8d9 2011-09-28 kinaba: #include <sstream> 14e544f8d9 2011-09-28 kinaba: #include <iomanip> 14e544f8d9 2011-09-28 kinaba: #include <vector> 14e544f8d9 2011-09-28 kinaba: #include <string> 14e544f8d9 2011-09-28 kinaba: #include <map> 14e544f8d9 2011-09-28 kinaba: #include <set> 14e544f8d9 2011-09-28 kinaba: #include <algorithm> 14e544f8d9 2011-09-28 kinaba: #include <numeric> 14e544f8d9 2011-09-28 kinaba: #include <iterator> 14e544f8d9 2011-09-28 kinaba: #include <functional> 14e544f8d9 2011-09-28 kinaba: #include <complex> 14e544f8d9 2011-09-28 kinaba: #include <queue> 14e544f8d9 2011-09-28 kinaba: #include <valarray> 14e544f8d9 2011-09-28 kinaba: #include <stack> 14e544f8d9 2011-09-28 kinaba: #include <cmath> 14e544f8d9 2011-09-28 kinaba: #include <cassert> 14e544f8d9 2011-09-28 kinaba: #include <cstring> 14e544f8d9 2011-09-28 kinaba: using namespace std; 14e544f8d9 2011-09-28 kinaba: typedef long long LL; 14e544f8d9 2011-09-28 kinaba: typedef complex<double> CMP; 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: static const int MODVAL = 1000000007; 14e544f8d9 2011-09-28 kinaba: struct mint 14e544f8d9 2011-09-28 kinaba: { 14e544f8d9 2011-09-28 kinaba: int val; 14e544f8d9 2011-09-28 kinaba: mint():val(0){} 14e544f8d9 2011-09-28 kinaba: mint(int x):val(x%MODVAL) {} 14e544f8d9 2011-09-28 kinaba: mint(size_t x):val(x%MODVAL) {} 14e544f8d9 2011-09-28 kinaba: mint(LL x):val(x%MODVAL) {} 14e544f8d9 2011-09-28 kinaba: }; 14e544f8d9 2011-09-28 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 14e544f8d9 2011-09-28 kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 14e544f8d9 2011-09-28 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 14e544f8d9 2011-09-28 kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 14e544f8d9 2011-09-28 kinaba: mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 14e544f8d9 2011-09-28 kinaba: mint operator+(mint x, mint y) { return x+=y; } 14e544f8d9 2011-09-28 kinaba: mint operator-(mint x, mint y) { return x-=y; } 14e544f8d9 2011-09-28 kinaba: mint operator*(mint x, mint y) { return x*=y; } 14e544f8d9 2011-09-28 kinaba: mint operator/(mint x, mint y) { return x/=y; } 14e544f8d9 2011-09-28 kinaba: mint inv2 = mint(1) / 2; 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: class Nim { public: 14e544f8d9 2011-09-28 kinaba: int count(int K, int L) 14e544f8d9 2011-09-28 kinaba: { 14e544f8d9 2011-09-28 kinaba: valarray<mint> v(65536); 14e544f8d9 2011-09-28 kinaba: v[slice(2,L-1,1)] = 1; 14e544f8d9 2011-09-28 kinaba: for(unsigned p=2; p<=L; ++p) 14e544f8d9 2011-09-28 kinaba: if( v[p].val ) 14e544f8d9 2011-09-28 kinaba: for(unsigned q=p*p; q<=L; q+=p) 14e544f8d9 2011-09-28 kinaba: v[q] = 0; 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: pre(v, 0, 65536); 14e544f8d9 2011-09-28 kinaba: valarray<mint> a(1, 65536); 14e544f8d9 2011-09-28 kinaba: for(int i=1; i<=K; i<<=1, v*=v) 14e544f8d9 2011-09-28 kinaba: if( K & i ) 14e544f8d9 2011-09-28 kinaba: a *= v; 14e544f8d9 2011-09-28 kinaba: post(a, 0, 65536); 14e544f8d9 2011-09-28 kinaba: return a[0].val; 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: void pre(valarray<mint>& v, int s, int e) 14e544f8d9 2011-09-28 kinaba: { 14e544f8d9 2011-09-28 kinaba: if( s+1 == e ) 14e544f8d9 2011-09-28 kinaba: return; 14e544f8d9 2011-09-28 kinaba: int m = (s+e)/2; 14e544f8d9 2011-09-28 kinaba: pre(v, s, m); 14e544f8d9 2011-09-28 kinaba: pre(v, m, e); 14e544f8d9 2011-09-28 kinaba: for(int i=s,j=m; i<m; ++i,++j) { 14e544f8d9 2011-09-28 kinaba: mint vi=v[i], vj=v[j]; 14e544f8d9 2011-09-28 kinaba: v[i] = vi - vj; 14e544f8d9 2011-09-28 kinaba: v[j] = vi + vj; 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: void post(valarray<mint>& v, int s, int e) 14e544f8d9 2011-09-28 kinaba: { 14e544f8d9 2011-09-28 kinaba: if( s+1 == e ) 14e544f8d9 2011-09-28 kinaba: return; 14e544f8d9 2011-09-28 kinaba: int m = (s+e)/2; 14e544f8d9 2011-09-28 kinaba: for(int i=s,j=m; i<m; ++i,++j) { 14e544f8d9 2011-09-28 kinaba: mint dif=v[i], sum=v[j]; 14e544f8d9 2011-09-28 kinaba: v[i] = (sum + dif) * inv2; 14e544f8d9 2011-09-28 kinaba: v[j] = (sum - dif) * inv2; 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: post(v, s, m); 14e544f8d9 2011-09-28 kinaba: post(v, m, e); 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: }; 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: // BEGIN CUT HERE 14e544f8d9 2011-09-28 kinaba: #include <ctime> 14e544f8d9 2011-09-28 kinaba: double start_time; string timer() 14e544f8d9 2011-09-28 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 14e544f8d9 2011-09-28 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 14e544f8d9 2011-09-28 kinaba: { os << "{ "; 14e544f8d9 2011-09-28 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 14e544f8d9 2011-09-28 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 14e544f8d9 2011-09-28 kinaba: void verify_case(const int& Expected, const int& Received) { 14e544f8d9 2011-09-28 kinaba: bool ok = (Expected == Received); 14e544f8d9 2011-09-28 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 14e544f8d9 2011-09-28 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 14e544f8d9 2011-09-28 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 14e544f8d9 2011-09-28 kinaba: #define END verify_case(_, Nim().count(K, L));} 14e544f8d9 2011-09-28 kinaba: int main(){ 14e544f8d9 2011-09-28 kinaba: 14e544f8d9 2011-09-28 kinaba: CASE(0) 14e544f8d9 2011-09-28 kinaba: int K = 3; 14e544f8d9 2011-09-28 kinaba: int L = 7; 14e544f8d9 2011-09-28 kinaba: int _ = 6; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: CASE(1) 14e544f8d9 2011-09-28 kinaba: int K = 4; 14e544f8d9 2011-09-28 kinaba: int L = 13; 14e544f8d9 2011-09-28 kinaba: int _ = 120; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: CASE(2) 14e544f8d9 2011-09-28 kinaba: int K = 10; 14e544f8d9 2011-09-28 kinaba: int L = 100; 14e544f8d9 2011-09-28 kinaba: int _ = 294844622; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: CASE(3) 14e544f8d9 2011-09-28 kinaba: int K = 123456789; 14e544f8d9 2011-09-28 kinaba: int L = 12345; 14e544f8d9 2011-09-28 kinaba: int _ = 235511047; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: CASE(4) 14e544f8d9 2011-09-28 kinaba: int K = 1000000000; 14e544f8d9 2011-09-28 kinaba: int L = 50000; 14e544f8d9 2011-09-28 kinaba: int _ = 428193537; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: /* 14e544f8d9 2011-09-28 kinaba: CASE(5) 14e544f8d9 2011-09-28 kinaba: int K = ; 14e544f8d9 2011-09-28 kinaba: int L = ; 14e544f8d9 2011-09-28 kinaba: int _ = ; 14e544f8d9 2011-09-28 kinaba: END 14e544f8d9 2011-09-28 kinaba: */ 14e544f8d9 2011-09-28 kinaba: } 14e544f8d9 2011-09-28 kinaba: // END CUT HERE