4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: static const int MODNUM = 1000000007; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // make [i,j) by k[z..$] 4fd800b3a8 2011-02-23 kinaba: LL dp[31][31][51][51]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class ReverseResources 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: int findDecompositions(string str, vector <string> resources) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: memset(dp, 0xff, sizeof(dp)); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: LL sum = 0; 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<resources.size(); ++k) 4fd800b3a8 2011-02-23 kinaba: sum = (sum + rec(0, str.size(), k, 0, str, resources, dp)) % MODNUM; 4fd800b3a8 2011-02-23 kinaba: return sum; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: LL rec(int i, int j, int k, int z, string& s, vector<string>& rs, LL dp[31][31][51][51] ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( dp[i][j][k][z] >= 0 ) 4fd800b3a8 2011-02-23 kinaba: return dp[i][j][k][z]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string& r = rs[k]; 4fd800b3a8 2011-02-23 kinaba: if( z==r.size() ) 4fd800b3a8 2011-02-23 kinaba: return dp[i][j][k][z] = (i==j ? 1 : 0); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( r[z] == '%' ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: LL sum = 0; 4fd800b3a8 2011-02-23 kinaba: if( z+2 == r.size() ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: for(int kk=0; kk<rs.size(); ++kk) 4fd800b3a8 2011-02-23 kinaba: sum = (sum + rec(i, j, kk, 0, s, rs, dp)) % MODNUM; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: for(int jj=i+1; jj<j; ++jj) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: LL right = rec(jj, j, k, z+2, s, rs, dp); 4fd800b3a8 2011-02-23 kinaba: if( right ) { 4fd800b3a8 2011-02-23 kinaba: LL left = 0; 4fd800b3a8 2011-02-23 kinaba: for(int kk=0; kk<rs.size(); ++kk) 4fd800b3a8 2011-02-23 kinaba: left = (left + rec(i, jj, kk, 0, s, rs, dp)) % MODNUM; 4fd800b3a8 2011-02-23 kinaba: sum = (sum + left*right) % MODNUM; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return dp[i][j][k][z] = sum; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( r[z]==s[i] && i+1<=j ) 4fd800b3a8 2011-02-23 kinaba: return dp[i][j][k][z] = rec(i+1,j,k,z+1,s,rs,dp); 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: return dp[i][j][k][z] = 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); } 4fd800b3a8 2011-02-23 kinaba: private: 4fd800b3a8 2011-02-23 kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: void test_case_0() { string Arg0 = "Error in module foo, code 123."; string Arr1[] = {"foo", "123", "Error in module %s.", "%s, code %s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 1; verify_case(0, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_1() { string Arg0 = "The fox jumped over the dog."; string Arr1[] = {"The fox %s over the dog.", 4fd800b3a8 2011-02-23 kinaba: "lazy", 4fd800b3a8 2011-02-23 kinaba: "brown", 4fd800b3a8 2011-02-23 kinaba: "jump%s", 4fd800b3a8 2011-02-23 kinaba: "s", 4fd800b3a8 2011-02-23 kinaba: "ed", 4fd800b3a8 2011-02-23 kinaba: "The %s", 4fd800b3a8 2011-02-23 kinaba: "fox %s", 4fd800b3a8 2011-02-23 kinaba: "%s over %s", 4fd800b3a8 2011-02-23 kinaba: "the dog."}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5; verify_case(1, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_2() { string Arg0 = "abcde"; string Arr1[] = {"%sc%s", "b", "de", "a%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_3() { string Arg0 = "abcde"; string Arr1[] = {"%se", "a%s", "%sb%s", "%sc%s", "%sd%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(3, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_4() { string Arg0 = "aaaaa"; string Arr1[] = {"a","%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 14; verify_case(4, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_5() { string Arg0 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; string Arr1[] = {"a","aa","%s%s","%sa","a%s","aaa","aa%s","a%sa", 4fd800b3a8 2011-02-23 kinaba: "a%s%s","%saa","%sa%s","%s%sa","%s%s%s","aaaa", 4fd800b3a8 2011-02-23 kinaba: "aaa%s","aa%sa","aa%s%s","a%saa","a%sa%s","a%s%sa", 4fd800b3a8 2011-02-23 kinaba: "a%s%s%s","%saaa","%saa%s","%sa%sa","%sa%s%s", 4fd800b3a8 2011-02-23 kinaba: "%s%saa","%s%sa%s","%s%s%sa","%s%s%s%s","aaaaa", 4fd800b3a8 2011-02-23 kinaba: "aaaa%s","aaa%sa","aaa%s%s","aa%saa","aa%sa%s", 4fd800b3a8 2011-02-23 kinaba: "aa%s%sa","aa%s%s%s","a%saaa","a%saa%s","a%sa%sa", 4fd800b3a8 2011-02-23 kinaba: "a%sa%s%s","a%s%saa","a%s%sa%s","a%s%s%sa", 4fd800b3a8 2011-02-23 kinaba: "a%s%s%s%s","%saaaa","%saaa%s","%saa%sa","%saa%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 879704799; verify_case(5, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_6() { string Arg0 = "aa"; string Arr1[] = {"a", "a", "%s%s", "%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 8; verify_case(6, Arg2, findDecompositions(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: int main() { ReverseResources().run_test(-1); } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE