6d771c8da1 2011-07-10 kinaba: #include <iostream> 6d771c8da1 2011-07-10 kinaba: #include <sstream> 6d771c8da1 2011-07-10 kinaba: #include <iomanip> 6d771c8da1 2011-07-10 kinaba: #include <vector> 6d771c8da1 2011-07-10 kinaba: #include <string> 6d771c8da1 2011-07-10 kinaba: #include <map> 6d771c8da1 2011-07-10 kinaba: #include <set> 6d771c8da1 2011-07-10 kinaba: #include <algorithm> 6d771c8da1 2011-07-10 kinaba: #include <numeric> 6d771c8da1 2011-07-10 kinaba: #include <iterator> 6d771c8da1 2011-07-10 kinaba: #include <functional> 6d771c8da1 2011-07-10 kinaba: #include <complex> 6d771c8da1 2011-07-10 kinaba: #include <queue> 6d771c8da1 2011-07-10 kinaba: #include <stack> 6d771c8da1 2011-07-10 kinaba: #include <cmath> 6d771c8da1 2011-07-10 kinaba: #include <cassert> 6d771c8da1 2011-07-10 kinaba: #include <cstring> 6d771c8da1 2011-07-10 kinaba: using namespace std; 6d771c8da1 2011-07-10 kinaba: typedef long long LL; 6d771c8da1 2011-07-10 kinaba: typedef complex<double> CMP; 6d771c8da1 2011-07-10 kinaba: 6d771c8da1 2011-07-10 kinaba: template<typename T> 6d771c8da1 2011-07-10 kinaba: struct DP3x 6d771c8da1 2011-07-10 kinaba: { 6d771c8da1 2011-07-10 kinaba: int N1, N2, N3; 6d771c8da1 2011-07-10 kinaba: vector<T> data; 6d771c8da1 2011-07-10 kinaba: DP3x(int, int N2, int N3, const T& t = T()) 6d771c8da1 2011-07-10 kinaba: : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); } 6d771c8da1 2011-07-10 kinaba: T& operator()(int i1, int i2, int i3) 6d771c8da1 2011-07-10 kinaba: { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } 6d771c8da1 2011-07-10 kinaba: }; 6d771c8da1 2011-07-10 kinaba: 6d771c8da1 2011-07-10 kinaba: static const int MODVAL = 1000000007; 6d771c8da1 2011-07-10 kinaba: 6d771c8da1 2011-07-10 kinaba: class RowOfColors { public: 6d771c8da1 2011-07-10 kinaba: int countWays(int w, int h, int k) 6d771c8da1 2011-07-10 kinaba: { 6d771c8da1 2011-07-10 kinaba: DP3x<LL> dp(w+1, h+1, k+1); 6d771c8da1 2011-07-10 kinaba: for(int i=w; i>=0; --i) 6d771c8da1 2011-07-10 kinaba: for(int stack=0; stack<=h; ++stack) 6d771c8da1 2011-07-10 kinaba: for(int used =0; used <=k; ++used) 6d771c8da1 2011-07-10 kinaba: if( i == w ) 6d771c8da1 2011-07-10 kinaba: dp(i,stack,used) = (stack==1 && used==k ? 1 : 0); 6d771c8da1 2011-07-10 kinaba: else { 6d771c8da1 2011-07-10 kinaba: LL cnt = 0; 6d771c8da1 2011-07-10 kinaba: if(stack+1<=h && used+1<=k) // push new color 6d771c8da1 2011-07-10 kinaba: cnt += dp(i+1,stack+1,used+1); 6d771c8da1 2011-07-10 kinaba: if(stack) // continue the same color 6d771c8da1 2011-07-10 kinaba: cnt += dp(i+1,stack,used); 6d771c8da1 2011-07-10 kinaba: if(stack && used+1<=k) // replace top 6d771c8da1 2011-07-10 kinaba: cnt += dp(i+1,stack,used+1); 6d771c8da1 2011-07-10 kinaba: if(stack>=2) // pop 6d771c8da1 2011-07-10 kinaba: cnt += dp(i+1,stack-1,used); 6d771c8da1 2011-07-10 kinaba: dp(i,stack,used) = cnt % MODVAL; 6d771c8da1 2011-07-10 kinaba: } 6d771c8da1 2011-07-10 kinaba: LL v = dp(0,0,0); 6d771c8da1 2011-07-10 kinaba: for(int i=1; i<=k; ++i) 6d771c8da1 2011-07-10 kinaba: v = (v*i) % MODVAL; 6d771c8da1 2011-07-10 kinaba: return int(v); 6d771c8da1 2011-07-10 kinaba: } 6d771c8da1 2011-07-10 kinaba: }; 6d771c8da1 2011-07-10 kinaba: 6d771c8da1 2011-07-10 kinaba: // BEGIN CUT HERE 6d771c8da1 2011-07-10 kinaba: #include <ctime> 6d771c8da1 2011-07-10 kinaba: double start_time; string timer() 6d771c8da1 2011-07-10 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 6d771c8da1 2011-07-10 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 6d771c8da1 2011-07-10 kinaba: { os << "{ "; 6d771c8da1 2011-07-10 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 6d771c8da1 2011-07-10 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 6d771c8da1 2011-07-10 kinaba: void verify_case(const int& Expected, const int& Received) { 6d771c8da1 2011-07-10 kinaba: bool ok = (Expected == Received); 6d771c8da1 2011-07-10 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 6d771c8da1 2011-07-10 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 6d771c8da1 2011-07-10 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 6d771c8da1 2011-07-10 kinaba: #define END verify_case(_, RowOfColors().countWays(w, h, k));} 6d771c8da1 2011-07-10 kinaba: int main(){ 6d771c8da1 2011-07-10 kinaba: 6d771c8da1 2011-07-10 kinaba: CASE(0) 6d771c8da1 2011-07-10 kinaba: int w = 4; 6d771c8da1 2011-07-10 kinaba: int h = 1; 6d771c8da1 2011-07-10 kinaba: int k = 2; 6d771c8da1 2011-07-10 kinaba: int _ = 6; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: CASE(1) 6d771c8da1 2011-07-10 kinaba: int w = 4; 6d771c8da1 2011-07-10 kinaba: int h = 3; 6d771c8da1 2011-07-10 kinaba: int k = 2; 6d771c8da1 2011-07-10 kinaba: int _ = 12; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: CASE(2) 6d771c8da1 2011-07-10 kinaba: int w = 4; 6d771c8da1 2011-07-10 kinaba: int h = 4; 6d771c8da1 2011-07-10 kinaba: int k = 10; 6d771c8da1 2011-07-10 kinaba: int _ = 0; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: CASE(3) 6d771c8da1 2011-07-10 kinaba: int w = 14; 6d771c8da1 2011-07-10 kinaba: int h = 28; 6d771c8da1 2011-07-10 kinaba: int k = 14; 6d771c8da1 2011-07-10 kinaba: int _ = 178290591; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: /* 6d771c8da1 2011-07-10 kinaba: CASE(4) 6d771c8da1 2011-07-10 kinaba: int w = ; 6d771c8da1 2011-07-10 kinaba: int h = ; 6d771c8da1 2011-07-10 kinaba: int k = ; 6d771c8da1 2011-07-10 kinaba: int _ = ; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: CASE(5) 6d771c8da1 2011-07-10 kinaba: int w = ; 6d771c8da1 2011-07-10 kinaba: int h = ; 6d771c8da1 2011-07-10 kinaba: int k = ; 6d771c8da1 2011-07-10 kinaba: int _ = ; 6d771c8da1 2011-07-10 kinaba: END 6d771c8da1 2011-07-10 kinaba: */ 6d771c8da1 2011-07-10 kinaba: } 6d771c8da1 2011-07-10 kinaba: // END CUT HERE