db58c713f6 2012-02-24 kinaba: #include <iostream> db58c713f6 2012-02-24 kinaba: #include <sstream> db58c713f6 2012-02-24 kinaba: #include <iomanip> db58c713f6 2012-02-24 kinaba: #include <vector> db58c713f6 2012-02-24 kinaba: #include <string> db58c713f6 2012-02-24 kinaba: #include <map> db58c713f6 2012-02-24 kinaba: #include <set> db58c713f6 2012-02-24 kinaba: #include <algorithm> db58c713f6 2012-02-24 kinaba: #include <numeric> db58c713f6 2012-02-24 kinaba: #include <iterator> db58c713f6 2012-02-24 kinaba: #include <functional> db58c713f6 2012-02-24 kinaba: #include <complex> db58c713f6 2012-02-24 kinaba: #include <queue> db58c713f6 2012-02-24 kinaba: #include <stack> db58c713f6 2012-02-24 kinaba: #include <cmath> db58c713f6 2012-02-24 kinaba: #include <cassert> db58c713f6 2012-02-24 kinaba: #include <cstring> db58c713f6 2012-02-24 kinaba: #ifdef __GNUC__ db58c713f6 2012-02-24 kinaba: #include <ext/hash_map> db58c713f6 2012-02-24 kinaba: #define unordered_map __gnu_cxx::hash_map db58c713f6 2012-02-24 kinaba: #else db58c713f6 2012-02-24 kinaba: #include <unordered_map> db58c713f6 2012-02-24 kinaba: #endif db58c713f6 2012-02-24 kinaba: using namespace std; db58c713f6 2012-02-24 kinaba: typedef long long LL; db58c713f6 2012-02-24 kinaba: typedef complex<double> CMP; db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: template<typename T> db58c713f6 2012-02-24 kinaba: struct DP3 db58c713f6 2012-02-24 kinaba: { db58c713f6 2012-02-24 kinaba: int N1, N2, N3; db58c713f6 2012-02-24 kinaba: vector<T> data; db58c713f6 2012-02-24 kinaba: DP3(int N1, int N2, int N3, const T& t = T()) db58c713f6 2012-02-24 kinaba: : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } db58c713f6 2012-02-24 kinaba: T& operator()(int i1, int i2, int i3) db58c713f6 2012-02-24 kinaba: { return data[ ((i1*N2)+i2)*N3+i3 ]; } db58c713f6 2012-02-24 kinaba: void swap(DP3& rhs) db58c713f6 2012-02-24 kinaba: { data.swap(rhs.data); } db58c713f6 2012-02-24 kinaba: }; db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: static const int MODVAL = 1000000007; // must be prime for op/ db58c713f6 2012-02-24 kinaba: struct mint db58c713f6 2012-02-24 kinaba: { db58c713f6 2012-02-24 kinaba: int val; db58c713f6 2012-02-24 kinaba: mint():val(0){} db58c713f6 2012-02-24 kinaba: mint(int x):val(x%MODVAL) {} // x>=0 db58c713f6 2012-02-24 kinaba: mint(size_t x):val(x%MODVAL) {} // x>=0 db58c713f6 2012-02-24 kinaba: mint(LL x):val(x%MODVAL) {} // x>=0 db58c713f6 2012-02-24 kinaba: }; db58c713f6 2012-02-24 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } db58c713f6 2012-02-24 kinaba: mint operator+(mint x, mint y) { return x+=y; } db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: class DengklekPaintingSquares { public: db58c713f6 2012-02-24 kinaba: int numSolutions(int N, int M) db58c713f6 2012-02-24 kinaba: { db58c713f6 2012-02-24 kinaba: int END=1; for(int i=0; i<M-1; ++i) END*=3; db58c713f6 2012-02-24 kinaba: DP3<int> memo(N, M, END*3, -1); db58c713f6 2012-02-24 kinaba: return rec(memo, N, M, END, -1, M, 0); db58c713f6 2012-02-24 kinaba: } db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: int rec(DP3<int>& memo, const int H, const int W, const int END, int y, int x, int state) db58c713f6 2012-02-24 kinaba: { db58c713f6 2012-02-24 kinaba: if( x == W ) db58c713f6 2012-02-24 kinaba: ++y, x=0; db58c713f6 2012-02-24 kinaba: if( y == H ) db58c713f6 2012-02-24 kinaba: return valid(state) ? 1 : 0; db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: if( memo(y,x,state)!=-1 ) db58c713f6 2012-02-24 kinaba: return memo(y,x,state); db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: mint total = 0; db58c713f6 2012-02-24 kinaba: int old = state%3; db58c713f6 2012-02-24 kinaba: int pre = state/END%3; db58c713f6 2012-02-24 kinaba: bool put=(old==0 || old==1), nut=(old==0 || old==2); db58c713f6 2012-02-24 kinaba: int parity = (old>=1) ^ (x==0 ? 0 : pre>=1); db58c713f6 2012-02-24 kinaba: if( x == 0 || pre == 0 ) { db58c713f6 2012-02-24 kinaba: if(put) total += rec(memo, H, W, END, y, x+1, state/3 + (2-parity)*END); db58c713f6 2012-02-24 kinaba: if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + 0*END); db58c713f6 2012-02-24 kinaba: } else { db58c713f6 2012-02-24 kinaba: if(put) total += rec(memo, H, W, END, y, x+1, (state-pre*END)/3 + (3-pre)*(END/3) + (2-parity)*END); db58c713f6 2012-02-24 kinaba: if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + 0*END); db58c713f6 2012-02-24 kinaba: } db58c713f6 2012-02-24 kinaba: return memo(y,x,state) = total.val; db58c713f6 2012-02-24 kinaba: } db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: bool valid(int state) db58c713f6 2012-02-24 kinaba: { db58c713f6 2012-02-24 kinaba: for(; state; state/=3) db58c713f6 2012-02-24 kinaba: if(state%3 == 1) db58c713f6 2012-02-24 kinaba: return false; db58c713f6 2012-02-24 kinaba: return true; db58c713f6 2012-02-24 kinaba: } db58c713f6 2012-02-24 kinaba: }; db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: // BEGIN CUT HERE db58c713f6 2012-02-24 kinaba: #include <ctime> db58c713f6 2012-02-24 kinaba: double start_time; string timer() db58c713f6 2012-02-24 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } db58c713f6 2012-02-24 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) db58c713f6 2012-02-24 kinaba: { os << "{ "; db58c713f6 2012-02-24 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) db58c713f6 2012-02-24 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } db58c713f6 2012-02-24 kinaba: void verify_case(const int& Expected, const int& Received) { db58c713f6 2012-02-24 kinaba: bool ok = (Expected == Received); db58c713f6 2012-02-24 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; db58c713f6 2012-02-24 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } db58c713f6 2012-02-24 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); db58c713f6 2012-02-24 kinaba: #define END verify_case(_, DengklekPaintingSquares().numSolutions(N, M));} db58c713f6 2012-02-24 kinaba: int main(){ db58c713f6 2012-02-24 kinaba: db58c713f6 2012-02-24 kinaba: CASE(0) db58c713f6 2012-02-24 kinaba: int N = 1; db58c713f6 2012-02-24 kinaba: int M = 1; db58c713f6 2012-02-24 kinaba: int _ = 2; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: CASE(1) db58c713f6 2012-02-24 kinaba: int N = 2; db58c713f6 2012-02-24 kinaba: int M = 2; db58c713f6 2012-02-24 kinaba: int _ = 8; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: CASE(2) db58c713f6 2012-02-24 kinaba: int N = 1; db58c713f6 2012-02-24 kinaba: int M = 3; db58c713f6 2012-02-24 kinaba: int _ = 5; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: CASE(3) db58c713f6 2012-02-24 kinaba: int N = 47; db58c713f6 2012-02-24 kinaba: int M = 7; db58c713f6 2012-02-24 kinaba: int _ = 944149920; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: CASE(4) db58c713f6 2012-02-24 kinaba: int N = 81; db58c713f6 2012-02-24 kinaba: int M = 8; db58c713f6 2012-02-24 kinaba: int _ = -1; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: /* db58c713f6 2012-02-24 kinaba: CASE(5) db58c713f6 2012-02-24 kinaba: int N = ; db58c713f6 2012-02-24 kinaba: int M = ; db58c713f6 2012-02-24 kinaba: int _ = ; db58c713f6 2012-02-24 kinaba: END db58c713f6 2012-02-24 kinaba: */ db58c713f6 2012-02-24 kinaba: } db58c713f6 2012-02-24 kinaba: // END CUT HERE