• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/686-U/1A.cpp version [ceaca236de3383b6]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class BracketSequenceDiv1 { public:
           23  + long long count(string s)
           24  + {
           25  +  return count_multi(s, 0, s.size()) - 1;
           26  + }
           27  +
           28  + map<pair<int,int>, LL> memo1;
           29  + LL count_multi(const string& str, int s, int e) {
           30  +  if(s == e)
           31  +   return 1;
           32  +  pair<int,int> key(s,e);
           33  +  if(memo1.count(key))
           34  +   return memo1[key];
           35  +
           36  +  LL total = 1;
           37  +  for(int m=s+2; m<=e; ++m)
           38  +   total += count_oneblock(str, s, m) * count_multi(str, m, e);
           39  +  return memo1[key] = total;
           40  + }
           41  +
           42  + map<pair<int,int>, LL> memo2;
           43  + LL count_oneblock(const string& str, int s, int e) {
           44  +  if(s == e)
           45  +   return 0;
           46  +  if(str[e-1]=='(' || str[e-1]=='[')
           47  +   return 0;
           48  +  const char op = (str[e-1]==')' ? '(' : '[');
           49  +
           50  +  pair<int,int> key(s,e);
           51  +  if(memo2.count(key))
           52  +   return memo2[key];
           53  +
           54  +  LL total = 0;
           55  +  for(int k=s; k<e; ++k)
           56  +   if(str[k] == op)
           57  +    total += count_multi(str, k+1, e-1);
           58  +  return memo2[key] = total;
           59  + }
           60  +};
           61  +
           62  +// BEGIN CUT HERE
           63  +#include <ctime>
           64  +double start_time; string timer()
           65  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           66  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           67  + { os << "{ ";
           68  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           69  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           70  +void verify_case(const long long& Expected, const long long& Received) {
           71  + bool ok = (Expected == Received);
           72  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           73  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           74  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           75  +#define END  verify_case(_, BracketSequenceDiv1().count(s));}
           76  +int main(){
           77  +
           78  +CASE(0)
           79  + string s = "()[]";
           80  + long long _ = 3LL;
           81  +END
           82  +CASE(1)
           83  + string s = "())";
           84  + long long _ = 2LL;
           85  +END
           86  +CASE(2)
           87  + string s = "()()";
           88  + long long _ = 4LL;
           89  +END
           90  +CASE(3)
           91  + string s = "([)]";
           92  + long long _ = 2LL;
           93  +END
           94  +CASE(4)
           95  + string s = "())[]][]([]()]]()]]]";
           96  + long long _ = 3854LL;
           97  +END
           98  +/*
           99  +CASE(5)
          100  + string s = ;
          101  + long long _ = LL;
          102  +END
          103  +CASE(6)
          104  + string s = ;
          105  + long long _ = LL;
          106  +END
          107  +*/
          108  +}
          109  +// END CUT HERE

Added SRM/686-U/1B-U.cpp version [eeebdace328178c2]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           38  +
           39  +class CyclesNumber { public:
           40  + vector <int> getExpectation(vector <int> n, vector <int> m)
           41  + {
           42  +  map<int, set<int>> q;
           43  +  for(int i=0; i<n.size(); ++i)
           44  +   q[n[i]].insert(m[i]);
           45  +
           46  +  map<pair<int,int>, int> ans;
           47  +  T(*max_element(n.begin(), n.end()), q, ans);
           48  +
           49  +  vector<int> result;
           50  +  for(int i=0; i<n.size(); ++i)
           51  +   result.push_back(ans[make_pair(n[i], m[i])]);
           52  +  return result;
           53  + }
           54  +
           55  + void T(int n, map<int,set<int>>& q, map<pair<int,int>,int>& ans)
           56  + {
           57  +  vector<mint> Si;
           58  +  Si.push_back(0);
           59  +  Si.push_back(1);
           60  +  for(int i=1; i<=n; ++i)
           61  +  {
           62  +   for(int m: q[i]) {
           63  +    mint total = 0;
           64  +    for(int f=0; f<Si.size(); ++f)
           65  +     total += POW(f, m) * Si[f];
           66  +    ans[make_pair(i,m)] = total.val;
           67  +   }
           68  +
           69  +   Si.resize(Si.size()+1);
           70  +   for(int k=Si.size()-1; k>=1; --k)
           71  +    Si[k] = Si[k]*i + Si[k-1];
           72  +  }
           73  + }
           74  +};
           75  +
           76  +// BEGIN CUT HERE
           77  +#include <ctime>
           78  +double start_time; string timer()
           79  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           80  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           81  + { os << "{ ";
           82  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           83  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           84  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           85  + bool ok = (Expected == Received);
           86  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           87  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           88  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           89  +#define END  verify_case(_, CyclesNumber().getExpectation(n, m));}
           90  +int main(){
           91  +CASE(0)
           92  + int n_[] = {2};
           93  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
           94  + int m_[] = {2};
           95  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
           96  + int __[] = {5 };
           97  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           98  +END
           99  +CASE(1)
          100  + int n_[] = {3};
          101  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
          102  + int m_[] = {0};
          103  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
          104  + int __[] = {6 };
          105  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          106  +END
          107  +CASE(2)
          108  + int n_[] = {1, 2, 3};
          109  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
          110  + int m_[] = {1, 3, 3};
          111  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
          112  + int __[] = {1, 9, 53 };
          113  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          114  +END
          115  +CASE(3)
          116  + int n_[] = {10, 20, 30};
          117  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
          118  + int m_[] = {10, 20, 30};
          119  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
          120  + int __[] = {586836447, 544389755, 327675273 };
          121  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          122  +END
          123  +CASE(4)
          124  +    int n_[] = {100000};
          125  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
          126  +    int m_[] = {300};
          127  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
          128  +    int __[] = {-1};
          129  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          130  +END
          131  +/*
          132  +CASE(5)
          133  + int n_[] = ;
          134  +   vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_));
          135  + int m_[] = ;
          136  +   vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_));
          137  + int __[] = ;
          138  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          139  +END
          140  +*/
          141  +}
          142  +// END CUT HERE