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

Added SRM/663-U/1A.cpp version [87d196ec5b1b86d8]

            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 ABBADiv1 { public:
           23  + string canObtain(string initial, string target)
           24  + {
           25  +  return can(target, initial) ? "Possible" : "Impossible";
           26  + }
           27  +
           28  + map<string, bool> memo;
           29  + bool can(const string& X, const string& S)
           30  + {
           31  +  if(X == S)
           32  +   return true;
           33  +  if(X.size() < S.size())
           34  +   return false;
           35  +  if(memo.count(X))
           36  +   return memo[X];
           37  +  if(X[X.size()-1] == 'A' && can(X.substr(0, X.size()-1), S)) return memo[X] = true;
           38  +  if(X[0] == 'B' && can(rev(X.substr(1, X.size())), S)) return memo[X] = true;
           39  +  return memo[X] = false;
           40  + }
           41  +
           42  + string rev(const string& x) { return string(x.rbegin(), x.rend()); }
           43  +};
           44  +
           45  +// BEGIN CUT HERE
           46  +#include <ctime>
           47  +double start_time; string timer()
           48  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           49  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           50  + { os << "{ ";
           51  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           52  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           53  +void verify_case(const string& Expected, const string& Received) {
           54  + bool ok = (Expected == Received);
           55  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           56  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           57  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           58  +#define END  verify_case(_, ABBADiv1().canObtain(initial, target));}
           59  +int main(){
           60  +
           61  +CASE(0)
           62  + string initial = "A";
           63  + string target = "BABA";
           64  + string _ = "Possible";
           65  +END
           66  +CASE(1)
           67  + string initial = "BAAAAABAA";
           68  + string target = "BAABAAAAAB";
           69  + string _ = "Possible";
           70  +END
           71  +CASE(2)
           72  + string initial = "A";
           73  + string target = "ABBA";
           74  + string _ = "Impossible";
           75  +END
           76  +CASE(3)
           77  + string initial = "AAABBAABB";
           78  + string target = "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB";
           79  + string _ = "Possible";
           80  +END
           81  +CASE(4)
           82  + string initial = "AAABAAABB";
           83  + string target = "BAABAAABAABAABBBAAAAAABBAABBBBBBBABB";
           84  + string _ = "Impossible";
           85  +END
           86  +/*
           87  +CASE(5)
           88  + string initial = ;
           89  + string target = ;
           90  + string _ = ;
           91  +END
           92  +CASE(6)
           93  + string initial = ;
           94  + string target = ;
           95  + string _ = ;
           96  +END
           97  +*/
           98  +}
           99  +// END CUT HERE

Added SRM/663-U/1B-U.cpp version [45e1815537ebc7d2]

            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  +
           38  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           39  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           40  +mint operator/(mint x, mint y) { return x/=y; }
           41  +
           42  +vector<mint> FAC_(1,1);
           43  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.size()) ); return FAC_[n]; }
           44  +
           45  +// nCk :: O(log MODVAL) time, O(n) space.
           46  +mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
           47  +
           48  +// nCk :: O(1) time, O(n^2) space.
           49  +vector< vector<mint> > CP_;
           50  +mint C(int n, int k) {
           51  + while( CP_.size() <= n ) {
           52  +  int nn = CP_.size();
           53  +  CP_.push_back(vector<mint>(nn+1,1));
           54  +  for(int kk=1; kk<nn; ++kk)
           55  +   CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
           56  + }
           57  + return k<0 || n<k ? 0 : CP_[n][k];
           58  +}
           59  +
           60  +class ChangingChange { public:
           61  + vector <int> countWays(vector <int> ways, vector <int> valueRemoved, vector <int> numRemoved)
           62  + {
           63  +  const int D = ways.size()-1;
           64  +
           65  +  vector<mint> coins(1, 0);
           66  +  for(int v=1; v<=D; ++v)
           67  +   coins.push_back(ways[v] - eval(coins,v));
           68  +
           69  +  vector<int> ans;
           70  +  for(int q=0; q<valueRemoved.size(); ++q) {
           71  +   const int v=valueRemoved[q], n=numRemoved[q];
           72  +   coins[v] -= n; // or += MODVAL-n, meaning mult (1+x^v)^(MODVAL-n)
           73  +   // then if cur is known and (1+x^v)^(MODVAL-n) is known,
           74  +   // O(D) to calc eval(coins,D)
           75  +   ans.push_back(eval(coins,D).val);
           76  +   coins[v] += n;
           77  +  }
           78  +  return ans;
           79  + }
           80  +
           81  + // Calc \Pi_v (1 + x^v)^c[v] 's coeefficient at x^D
           82  + //   c[v] may be very large
           83  + //   D <= 2000
           84  + //   v <= 2000
           85  + mint eval(const vector<mint>& c, int D)
           86  + {
           87  +  vector<mint> cur(D+1, 0);
           88  +  cur[0] = 1;
           89  +  for(int v=1; v<c.size(); ++v) {
           90  +   cur = polymul(cur, polypow(v, c[v].val, D), D);
           91  +  }
           92  +  return D<cur.size() ? cur[D] : 0;
           93  + }
           94  +
           95  + vector<mint> polymul(const vector<mint>& a, const vector<mint>& b, int D)
           96  + {
           97  +  int maxD = max<int>(D, (a.size()-1)*(b.size()-1));
           98  +  vector<mint> c(maxD+1);
           99  +  for(int i=0; i<a.size(); ++i)
          100  +  for(int k=0; k<b.size(); ++k)
          101  +   if(i+k<=maxD)
          102  +    c[i+k] += a[i]*b[k];
          103  +  return c;
          104  + }
          105  + vector<mint> polypow(int V, int K, int D)
          106  + {
          107  +  vector<mint> poly;
          108  +  // (1+x^V)^K upto x^D
          109  +  mint Ckd = 1;
          110  +  for(int d=0; d<=K; ++d) {
          111  +   LL dd = LL(d)*V;
          112  +   if(dd > D)
          113  +    break;
          114  +   poly.resize(int(dd)+1);
          115  +   poly[int(dd)] = Ckd;
          116  +
          117  +   Ckd *= (K-d);
          118  +   Ckd /= (d+1);
          119  +  }
          120  +  return poly;
          121  + }
          122  +};
          123  +
          124  +// BEGIN CUT HERE
          125  +#include <ctime>
          126  +double start_time; string timer()
          127  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          128  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          129  + { os << "{ ";
          130  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          131  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          132  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
          133  + bool ok = (Expected == Received);
          134  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          135  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          136  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          137  +#define END  verify_case(_, ChangingChange().countWays(ways, valueRemoved, numRemoved));}
          138  +int main(){
          139  +
          140  +CASE(0)
          141  + int ways_[] = {1, 4, 6};
          142  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          143  + int valueRemoved_[] = {1, 1, 1};
          144  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          145  + int numRemoved_[] = {1, 2, 3};
          146  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          147  + int __[] = {3, 1, 0 };
          148  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          149  +END
          150  +CASE(1)
          151  + int ways_[] = {1, 2, 1, 0, 0, 0, 0, 0, 7};
          152  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          153  + int valueRemoved_[] = {8, 8, 1, 1};
          154  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          155  + int numRemoved_[] = {1, 7, 1, 2};
          156  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          157  + int __[] = {6, 0, 7, 7 };
          158  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          159  +END
          160  +CASE(2)
          161  + int ways_[] = {1, 2, 3, 6, 9, 14};
          162  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          163  + int valueRemoved_[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
          164  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          165  + int numRemoved_[] = {1, 1, 1, 1, 1, 2, 2, 2, 2, 2};
          166  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          167  + int __[] = {9, 10, 11, 12, 13, 6, 8, 8, 10, 12 };
          168  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          169  +END
          170  +CASE(3)
          171  + int ways_[] = {1, 0};
          172  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          173  + int valueRemoved_[] = {1, 1};
          174  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          175  + int numRemoved_[] = {1, 1000000};
          176  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          177  + int __[] = {1000000006, 999000007 };
          178  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          179  +END
          180  +CASE(4)
          181  + int ways_[] = {1, 2, 3, 6, 9, 14};
          182  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          183  + int valueRemoved_[] = {1, 3, 5};
          184  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          185  + int numRemoved_[] = {1000000, 4, 2};
          186  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          187  + int __[] = {34955525, 2, 12 };
          188  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          189  +END
          190  +/*
          191  +CASE(5)
          192  + int ways_[] = ;
          193  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          194  + int valueRemoved_[] = ;
          195  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          196  + int numRemoved_[] = ;
          197  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          198  + int __[] = ;
          199  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          200  +END
          201  +CASE(6)
          202  + int ways_[] = ;
          203  +   vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_));
          204  + int valueRemoved_[] = ;
          205  +   vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_));
          206  + int numRemoved_[] = ;
          207  +   vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_));
          208  + int __[] = ;
          209  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          210  +END
          211  +*/
          212  +}
          213  +// END CUT HERE

Modified lib/numeric/modArith.cpp from [c76c99fca94dfde1] to [d49aef5cfc6580a0].

    25     25   mint operator*(mint x, mint y) { return x*=y; }
    26     26   
    27     27   mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
    28     28   mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
    29     29   mint operator/(mint x, mint y) { return x/=y; }
    30     30   
    31     31   vector<mint> FAC_(1,1);
    32         -mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           32  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.size()) ); return FAC_[n]; }
    33     33   
    34     34   // nCk :: O(log MODVAL) time, O(n) space.
    35     35   mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
    36     36   
    37     37   // nCk :: O(1) time, O(n^2) space.
    38     38   vector< vector<mint> > CP_;
    39     39   mint C(int n, int k) {