c5054cb313 2011-07-26 kinaba: #include <iostream> c5054cb313 2011-07-26 kinaba: #include <sstream> c5054cb313 2011-07-26 kinaba: #include <iomanip> c5054cb313 2011-07-26 kinaba: #include <vector> c5054cb313 2011-07-26 kinaba: #include <string> c5054cb313 2011-07-26 kinaba: #include <map> c5054cb313 2011-07-26 kinaba: #include <set> c5054cb313 2011-07-26 kinaba: #include <algorithm> c5054cb313 2011-07-26 kinaba: #include <numeric> c5054cb313 2011-07-26 kinaba: #include <iterator> c5054cb313 2011-07-26 kinaba: #include <functional> c5054cb313 2011-07-26 kinaba: #include <complex> c5054cb313 2011-07-26 kinaba: #include <queue> c5054cb313 2011-07-26 kinaba: #include <stack> c5054cb313 2011-07-26 kinaba: #include <cmath> c5054cb313 2011-07-26 kinaba: #include <cassert> c5054cb313 2011-07-26 kinaba: #include <cstring> c5054cb313 2011-07-26 kinaba: using namespace std; c5054cb313 2011-07-26 kinaba: typedef long long LL; c5054cb313 2011-07-26 kinaba: typedef complex<double> CMP; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: static const int MODVAL = 1000000007; c5054cb313 2011-07-26 kinaba: LL C[201][201]; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: class PickAndDelete { public: c5054cb313 2011-07-26 kinaba: int count(vector <string> S_) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: init_C(); c5054cb313 2011-07-26 kinaba: vector<int> S; c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: string s = accumulate(S_.begin(), S_.end(), string("")); c5054cb313 2011-07-26 kinaba: stringstream ss(s); c5054cb313 2011-07-26 kinaba: for(int v; ss>>v; ) c5054cb313 2011-07-26 kinaba: S.push_back(v); c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: sort(S.begin(), S.end()); c5054cb313 2011-07-26 kinaba: return solve(S); c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: void init_C() c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: for(int n=0; n<=200; ++n) c5054cb313 2011-07-26 kinaba: for(int k=0; k<=n; ++k) c5054cb313 2011-07-26 kinaba: if( k==0 || k==n ) c5054cb313 2011-07-26 kinaba: C[n][k] = 1; c5054cb313 2011-07-26 kinaba: else c5054cb313 2011-07-26 kinaba: C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MODVAL; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: int solve(const vector<int>& S) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: map<multiset<int>, LL> dp; c5054cb313 2011-07-26 kinaba: dp[multiset<int>()] = 1; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: for(int i=0; i<S.size(); ++i) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: int next = S[i]; c5054cb313 2011-07-26 kinaba: map<multiset<int>, LL> dp2; c5054cb313 2011-07-26 kinaba: for(map<multiset<int>,LL>::iterator it=dp.begin(); it!=dp.end(); ++it) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: const multiset<int>& sig = it->first; c5054cb313 2011-07-26 kinaba: if( sig.size() < next ) { c5054cb313 2011-07-26 kinaba: multiset<int> new_sig = sig; c5054cb313 2011-07-26 kinaba: new_sig.insert(1); c5054cb313 2011-07-26 kinaba: (dp2[new_sig] += it->second*(next-sig.size())) %= MODVAL; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: for(multiset<int>::const_iterator jt=sig.begin(); jt!=sig.end(); ++jt) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: multiset<int> new_sig = sig; c5054cb313 2011-07-26 kinaba: new_sig.erase(*jt); c5054cb313 2011-07-26 kinaba: new_sig.insert(*jt+1); c5054cb313 2011-07-26 kinaba: (dp2[new_sig] += it->second) %= MODVAL; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: dp.swap(dp2); c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: LL sum = 0; c5054cb313 2011-07-26 kinaba: for(map<multiset<int>,LL>::iterator it=dp.begin(); it!=dp.end(); ++it) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: LL n = it->second; c5054cb313 2011-07-26 kinaba: int tt = S.size(); c5054cb313 2011-07-26 kinaba: for(multiset<int>::const_iterator jt=it->first.begin(); jt!=it->first.end(); ++jt) { c5054cb313 2011-07-26 kinaba: (n *= C[tt][*jt]) %= MODVAL; c5054cb313 2011-07-26 kinaba: tt -= *jt; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: sum += n; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: return int(sum % MODVAL); c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: }; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: // BEGIN CUT HERE c5054cb313 2011-07-26 kinaba: #include <ctime> c5054cb313 2011-07-26 kinaba: double start_time; string timer() c5054cb313 2011-07-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c5054cb313 2011-07-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c5054cb313 2011-07-26 kinaba: { os << "{ "; c5054cb313 2011-07-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c5054cb313 2011-07-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c5054cb313 2011-07-26 kinaba: void verify_case(const int& Expected, const int& Received) { c5054cb313 2011-07-26 kinaba: bool ok = (Expected == Received); c5054cb313 2011-07-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c5054cb313 2011-07-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c5054cb313 2011-07-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c5054cb313 2011-07-26 kinaba: #define END verify_case(_, PickAndDelete().count(S));} c5054cb313 2011-07-26 kinaba: int main(){ c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: CASE(0) c5054cb313 2011-07-26 kinaba: string S_[] = {"1 2"}; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 3; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(1) c5054cb313 2011-07-26 kinaba: string S_[] = {"2 2 2 2 2 2 2 2 2"}; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 512; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(2) c5054cb313 2011-07-26 kinaba: string S_[] = {"5", " 1 ", "2"}; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 34; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(3) c5054cb313 2011-07-26 kinaba: string S_[] = {"3 ", "14159 265", "3589 7", " 932"}; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = 353127147; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: /* c5054cb313 2011-07-26 kinaba: CASE(4) c5054cb313 2011-07-26 kinaba: string S_[] = ; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = ; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(5) c5054cb313 2011-07-26 kinaba: string S_[] = ; c5054cb313 2011-07-26 kinaba: vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); c5054cb313 2011-07-26 kinaba: int _ = ; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: */ c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: // END CUT HERE