0b26cb3f9a 2012-05-29 kinaba: #include <iostream> 0b26cb3f9a 2012-05-29 kinaba: #include <sstream> 0b26cb3f9a 2012-05-29 kinaba: #include <iomanip> 0b26cb3f9a 2012-05-29 kinaba: #include <vector> 0b26cb3f9a 2012-05-29 kinaba: #include <string> 0b26cb3f9a 2012-05-29 kinaba: #include <map> 0b26cb3f9a 2012-05-29 kinaba: #include <set> 0b26cb3f9a 2012-05-29 kinaba: #include <algorithm> 0b26cb3f9a 2012-05-29 kinaba: #include <numeric> 0b26cb3f9a 2012-05-29 kinaba: #include <iterator> 0b26cb3f9a 2012-05-29 kinaba: #include <functional> 0b26cb3f9a 2012-05-29 kinaba: #include <complex> 0b26cb3f9a 2012-05-29 kinaba: #include <queue> 0b26cb3f9a 2012-05-29 kinaba: #include <stack> 0b26cb3f9a 2012-05-29 kinaba: #include <cmath> 0b26cb3f9a 2012-05-29 kinaba: #include <cassert> 0b26cb3f9a 2012-05-29 kinaba: using namespace std; 0b26cb3f9a 2012-05-29 kinaba: typedef long long LL; 0b26cb3f9a 2012-05-29 kinaba: typedef long double LD; 0b26cb3f9a 2012-05-29 kinaba: typedef complex<LD> CMP; 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: static const int MODVAL = 1000000007; // must be prime for op/ 0b26cb3f9a 2012-05-29 kinaba: struct mint 0b26cb3f9a 2012-05-29 kinaba: { 0b26cb3f9a 2012-05-29 kinaba: int val; 0b26cb3f9a 2012-05-29 kinaba: mint():val(0){} 0b26cb3f9a 2012-05-29 kinaba: mint(int x):val(x%MODVAL) {} // x>=0 0b26cb3f9a 2012-05-29 kinaba: mint(size_t x):val(x%MODVAL) {} // x>=0 0b26cb3f9a 2012-05-29 kinaba: mint(LL x):val(x%MODVAL) {} // x>=0 0b26cb3f9a 2012-05-29 kinaba: }; 0b26cb3f9a 2012-05-29 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 0b26cb3f9a 2012-05-29 kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 0b26cb3f9a 2012-05-29 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 0b26cb3f9a 2012-05-29 kinaba: mint operator+(mint x, mint y) { return x+=y; } 0b26cb3f9a 2012-05-29 kinaba: mint operator-(mint x, mint y) { return x-=y; } 0b26cb3f9a 2012-05-29 kinaba: mint operator*(mint x, mint y) { return x*=y; } 0b26cb3f9a 2012-05-29 kinaba: mint operator-(mint x) { return mint(0) - x; } 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: vector<mint> vMul( const vector< vector<mint> >& A, const vector<mint>& B ) 0b26cb3f9a 2012-05-29 kinaba: { 0b26cb3f9a 2012-05-29 kinaba: const int n = A.size(); 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: vector<mint> C(n); 0b26cb3f9a 2012-05-29 kinaba: for(int i=0; i<n; ++i) 0b26cb3f9a 2012-05-29 kinaba: for(int j=0; j<n; ++j) 0b26cb3f9a 2012-05-29 kinaba: C[i] += A[i][j] * B[j]; 0b26cb3f9a 2012-05-29 kinaba: return C; 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: vector< vector<mint> > mMul( const vector< vector<mint> >& A, const vector< vector<mint> >& B ) 0b26cb3f9a 2012-05-29 kinaba: { 0b26cb3f9a 2012-05-29 kinaba: const int n = A.size(); 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: vector< vector<mint> > C(n, vector<mint>(n)); 0b26cb3f9a 2012-05-29 kinaba: for(int i=0; i<n; ++i) 0b26cb3f9a 2012-05-29 kinaba: for(int j=0; j<n; ++j) { 0b26cb3f9a 2012-05-29 kinaba: mint Cij = 0; 0b26cb3f9a 2012-05-29 kinaba: for(int k=0; k<n; ++k) 0b26cb3f9a 2012-05-29 kinaba: Cij += A[i][k] * B[k][j]; 0b26cb3f9a 2012-05-29 kinaba: C[i][j] = Cij; 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: return C; 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: vector< vector<mint> > mPow( vector< vector<mint> > M, LL t ) // t>0 0b26cb3f9a 2012-05-29 kinaba: { 0b26cb3f9a 2012-05-29 kinaba: vector< vector<mint> > R; 0b26cb3f9a 2012-05-29 kinaba: for(; t; t>>=1, M=mMul(M,M)) 0b26cb3f9a 2012-05-29 kinaba: if( t&1 ) 0b26cb3f9a 2012-05-29 kinaba: R = (R.empty() ? M : mMul(R,M)); 0b26cb3f9a 2012-05-29 kinaba: return R; 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: class SplittingFoxes { public: 0b26cb3f9a 2012-05-29 kinaba: int sum(long long n, int S_, int L_, int R_) 0b26cb3f9a 2012-05-29 kinaba: { 0b26cb3f9a 2012-05-29 kinaba: mint S(S_), L(L_), R(R_); 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: enum {PR, PT, PL, PB, XR, XT, XL, XB, YR, YT, YL, YB, __}; 0b26cb3f9a 2012-05-29 kinaba: vector< vector<mint> > M(13, vector<mint>(13)); 0b26cb3f9a 2012-05-29 kinaba: M[PR][PR] = S; M[PR][YR] = S; M[PR][PT] = L; M[PR][PB] = R; 0b26cb3f9a 2012-05-29 kinaba: M[PT][PT] = S; M[PT][XT] = S; M[PT][PL] = L; M[PT][PR] = R; 0b26cb3f9a 2012-05-29 kinaba: M[PL][PL] = S; M[PL][YL] =-S; M[PL][PB] = L; M[PL][PT] = R; 0b26cb3f9a 2012-05-29 kinaba: M[PB][PB] = S; M[PB][XB] =-S; M[PB][PR] = L; M[PB][PL] = R; 0b26cb3f9a 2012-05-29 kinaba: M[XR][XR] = S; M[XR][__] = S; M[XR][XT] = L; M[XR][XB] = R; 0b26cb3f9a 2012-05-29 kinaba: M[XT][XT] = S; M[XT][__] = 0; M[XT][XL] = L; M[XT][XR] = R; 0b26cb3f9a 2012-05-29 kinaba: M[XL][XL] = S; M[XL][__] =-S; M[XL][XB] = L; M[XL][XT] = R; 0b26cb3f9a 2012-05-29 kinaba: M[XB][XB] = S; M[XB][__] = 0; M[XB][XR] = L; M[XB][XL] = R; 0b26cb3f9a 2012-05-29 kinaba: M[YR][YR] = S; M[YR][__] = 0; M[YR][YT] = L; M[YR][YB] = R; 0b26cb3f9a 2012-05-29 kinaba: M[YT][YT] = S; M[YT][__] = S; M[YT][YL] = L; M[YT][YR] = R; 0b26cb3f9a 2012-05-29 kinaba: M[YL][YL] = S; M[YL][__] = 0; M[YL][YB] = L; M[YL][YT] = R; 0b26cb3f9a 2012-05-29 kinaba: M[YB][YB] = S; M[YB][__] =-S; M[YB][YR] = L; M[YB][YL] = R; 0b26cb3f9a 2012-05-29 kinaba: M[__][__] = S+L+R; 0b26cb3f9a 2012-05-29 kinaba: vector<mint> V(13); 0b26cb3f9a 2012-05-29 kinaba: V[__] = 1; 0b26cb3f9a 2012-05-29 kinaba: return vMul(mPow(M, n), V)[PR].val; 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: }; 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: // BEGIN CUT HERE 0b26cb3f9a 2012-05-29 kinaba: #include <ctime> 0b26cb3f9a 2012-05-29 kinaba: double start_time; string timer() 0b26cb3f9a 2012-05-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 0b26cb3f9a 2012-05-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 0b26cb3f9a 2012-05-29 kinaba: { os << "{ "; 0b26cb3f9a 2012-05-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 0b26cb3f9a 2012-05-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 0b26cb3f9a 2012-05-29 kinaba: void verify_case(const int& Expected, const int& Received) { 0b26cb3f9a 2012-05-29 kinaba: bool ok = (Expected == Received); 0b26cb3f9a 2012-05-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 0b26cb3f9a 2012-05-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 0b26cb3f9a 2012-05-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 0b26cb3f9a 2012-05-29 kinaba: #define END verify_case(_, SplittingFoxes().sum(n, S, L, R));} 0b26cb3f9a 2012-05-29 kinaba: int main(){ 0b26cb3f9a 2012-05-29 kinaba: 0b26cb3f9a 2012-05-29 kinaba: CASE(0) 0b26cb3f9a 2012-05-29 kinaba: long long n = 58LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 2; 0b26cb3f9a 2012-05-29 kinaba: int L = 0; 0b26cb3f9a 2012-05-29 kinaba: int R = 0; 0b26cb3f9a 2012-05-29 kinaba: int _ = 0; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(1) 0b26cb3f9a 2012-05-29 kinaba: long long n = 3LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 1; 0b26cb3f9a 2012-05-29 kinaba: int L = 1; 0b26cb3f9a 2012-05-29 kinaba: int R = 0; 0b26cb3f9a 2012-05-29 kinaba: int _ = 1; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(2) 0b26cb3f9a 2012-05-29 kinaba: long long n = 5LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 1; 0b26cb3f9a 2012-05-29 kinaba: int L = 3; 0b26cb3f9a 2012-05-29 kinaba: int R = 2; 0b26cb3f9a 2012-05-29 kinaba: int _ = 34; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(3) 0b26cb3f9a 2012-05-29 kinaba: long long n = 5LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 1; 0b26cb3f9a 2012-05-29 kinaba: int L = 2; 0b26cb3f9a 2012-05-29 kinaba: int R = 3; 0b26cb3f9a 2012-05-29 kinaba: int _ = 999999973; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(4) 0b26cb3f9a 2012-05-29 kinaba: long long n = 123456789LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 987654321; 0b26cb3f9a 2012-05-29 kinaba: int L = 544; 0b26cb3f9a 2012-05-29 kinaba: int R = 544; 0b26cb3f9a 2012-05-29 kinaba: int _ = 0; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(5) 0b26cb3f9a 2012-05-29 kinaba: long long n = 65536LL; 0b26cb3f9a 2012-05-29 kinaba: int S = 1024; 0b26cb3f9a 2012-05-29 kinaba: int L = 512; 0b26cb3f9a 2012-05-29 kinaba: int R = 4096; 0b26cb3f9a 2012-05-29 kinaba: int _ = 371473914; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: /* 0b26cb3f9a 2012-05-29 kinaba: CASE(6) 0b26cb3f9a 2012-05-29 kinaba: long long n = LL; 0b26cb3f9a 2012-05-29 kinaba: int S = ; 0b26cb3f9a 2012-05-29 kinaba: int L = ; 0b26cb3f9a 2012-05-29 kinaba: int R = ; 0b26cb3f9a 2012-05-29 kinaba: int _ = ; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: CASE(7) 0b26cb3f9a 2012-05-29 kinaba: long long n = LL; 0b26cb3f9a 2012-05-29 kinaba: int S = ; 0b26cb3f9a 2012-05-29 kinaba: int L = ; 0b26cb3f9a 2012-05-29 kinaba: int R = ; 0b26cb3f9a 2012-05-29 kinaba: int _ = ; 0b26cb3f9a 2012-05-29 kinaba: END 0b26cb3f9a 2012-05-29 kinaba: */ 0b26cb3f9a 2012-05-29 kinaba: } 0b26cb3f9a 2012-05-29 kinaba: // END CUT HERE