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

Modified CheckList.pptx from [41156cd7a947e2a7] to [dcb9bdddd36bb3bb].

cannot compute difference between binary files

Added SRM/398/2C.cpp version [f85d7cb8c1261a54]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class MatchString { public:
           23  + int placeWords(string matchString, vector <string> matchWords)
           24  + {
           25  +  const int N = matchString.size();
           26  +  vector< vector<int> > idx(N);
           27  +  set<int> all_idx;
           28  +
           29  +  for(int i=0; i<N; ++i)
           30  +  {
           31  +   for(int j=0; j<matchWords[i].size(); ++j)
           32  +    if( matchWords[i][j] == matchString[i] )
           33  +    {
           34  +     idx[i].push_back(j);
           35  +     all_idx.insert(j);
           36  +    }
           37  +   if( idx[i].empty() )
           38  +    return -1;
           39  +  }
           40  +
           41  +  int best = INT_MAX;
           42  +  for(set<int>::iterator it=all_idx.begin(); it!=all_idx.end(); ++it)
           43  +  {
           44  +   int T = *it;
           45  +   int score = 0;
           46  +   for(int i=0; i<N; ++i)
           47  +   {
           48  +    int bb = INT_MAX;
           49  +    for(int j=0; j<idx[i].size(); ++j)
           50  +     if( idx[i][j] <= T )
           51  +      bb = min(bb, T-idx[i][j]);
           52  +    if( bb == INT_MAX )
           53  +     goto next;
           54  +    score += bb;
           55  +   }
           56  +   best = min(best, score);
           57  +  next:;
           58  +  }
           59  +  return best;
           60  + }
           61  +};
           62  +
           63  +// BEGIN CUT HERE
           64  +#include <ctime>
           65  +double start_time; string timer()
           66  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           67  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           68  + { os << "{ ";
           69  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           70  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           71  +void verify_case(const int& Expected, const int& Received) {
           72  + bool ok = (Expected == Received);
           73  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           74  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           75  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           76  +#define END  verify_case(_, MatchString().placeWords(matchString, matchWords));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + string matchString = "TOP";
           81  + string matchWords_[] = {"TIK",
           82  + "PPPO",
           83  + "OP"};
           84  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
           85  + int _ = 5;
           86  +END
           87  +CASE(1)
           88  + string matchString = "EEA";
           89  + string matchWords_[] = {"GEGA",
           90  + "TOPCODER",
           91  + "TEST"};
           92  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
           93  + int _ = -1;
           94  +END
           95  +CASE(2)
           96  + string matchString = "AB";
           97  + string matchWords_[] = {"ABA",
           98  + "ABAB"};
           99  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
          100  + int _ = 1;
          101  +END
          102  +CASE(3)
          103  + string matchString = "FIND";
          104  + string matchWords_[] = {"VERYFAST",
          105  + "OPINION",
          106  + "SPENDING",
          107  + "ODD"};
          108  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
          109  + int _ = 3;
          110  +END
          111  +CASE(4)
          112  + string matchString = "TOP";
          113  + string matchWords_[] = {"OUTTHERE",
          114  + "FROM",
          115  + "NOPQRSTU"};
          116  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
          117  + int _ = 0;
          118  +END
          119  +/*
          120  +CASE(5)
          121  + string matchString = ;
          122  + string matchWords_[] = ;
          123  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
          124  + int _ = ;
          125  +END
          126  +CASE(6)
          127  + string matchString = ;
          128  + string matchWords_[] = ;
          129  +   vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_)/sizeof(*matchWords_));
          130  + int _ = ;
          131  +END
          132  +*/
          133  +}
          134  +// END CUT HERE

Added SRM/499-U/1A.cpp version [1b6c222f9c3582e7]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ColorfulRabbits { public:
           23  + int getMinimum(vector <int> replies)
           24  + {
           25  +  map<int,int> m;
           26  +  for(int i=0; i<replies.size(); ++i)
           27  +   m[replies[i]]++;
           28  +  int total = 0;
           29  +  for(map<int,int>::iterator it=m.begin(); it!=m.end(); ++it)
           30  +  {
           31  +   int s = it->first + 1;
           32  +   int n = it->second;
           33  +   total += (n+s-1) / s * s;
           34  +  }
           35  +  return total;
           36  + }
           37  +};
           38  +
           39  +// BEGIN CUT HERE
           40  +#include <ctime>
           41  +double start_time; string timer()
           42  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           43  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           44  + { os << "{ ";
           45  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           46  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           47  +void verify_case(const int& Expected, const int& Received) {
           48  + bool ok = (Expected == Received);
           49  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           50  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           51  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           52  +#define END  verify_case(_, ColorfulRabbits().getMinimum(replies));}
           53  +int main(){
           54  +
           55  +CASE(0)
           56  + int replies_[] = { 1, 1, 2, 2 }
           57  +;
           58  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           59  + int _ = 5;
           60  +END
           61  +CASE(1)
           62  + int replies_[] = { 0 }
           63  +;
           64  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           65  + int _ = 1;
           66  +END
           67  +CASE(2)
           68  + int replies_[] = { 2, 2, 44, 2, 2, 2, 444, 2, 2 }
           69  +;
           70  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           71  + int _ = 499;
           72  +END
           73  +CASE(3)
           74  + int replies_[] = {1};
           75  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           76  + int _ = 2;
           77  +END
           78  +CASE(4)
           79  + int replies_[] = {2};
           80  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           81  + int _ = 3;
           82  +END
           83  +CASE(5)
           84  + int replies_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000};
           85  +   vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_));
           86  + int _ = -1;
           87  +END
           88  +
           89  +}
           90  +// END CUT HERE

Added SRM/499-U/1B-U.cpp version [13e543b5a0b1db44]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class WhiteSpaceEditing { public:
           23  + int getMinimum(vector <int> lines)
           24  + {
           25  +  const int N = lines.size();
           26  +  const int V = *max_element(lines.begin(), lines.end());
           27  +  vector<int> dp(V+1), dp_neo(V+1);
           28  +  for(int v=0; v<=V; ++v)
           29  +   dp[v] = abs(v - lines[N-1]);
           30  +  for(int i=N-2; i>=0; --i)
           31  +  {
           32  +   int best = INT_MAX;
           33  +   for(int v=lines[i]; v>=0; --v) {
           34  +    best = min(best, dp[v]);
           35  +    dp_neo[v] = abs(v - lines[i]) + best;
           36  +   }
           37  +   best = INT_MAX;
           38  +   for(int v=lines[i]; v<=V; ++v) {
           39  +    best = min(best, dp[v]);
           40  +    dp_neo[v] = abs(v - lines[i]) + best;
           41  +   }
           42  +   dp.swap(dp_neo);
           43  +  }
           44  +  return dp[0] + N-1;
           45  + }
           46  +};
           47  +
           48  +// BEGIN CUT HERE
           49  +#include <ctime>
           50  +double start_time; string timer()
           51  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           52  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           53  + { os << "{ ";
           54  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           55  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           56  +void verify_case(const int& Expected, const int& Received) {
           57  + bool ok = (Expected == Received);
           58  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           59  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           60  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           61  +#define END  verify_case(_, WhiteSpaceEditing().getMinimum(lines));}
           62  +int main(){
           63  +
           64  +CASE(0)
           65  + int lines_[] = { 3, 2, 3 };
           66  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           67  + int _ = 6;
           68  +END
           69  +CASE(1)
           70  + int lines_[] = { 0 };
           71  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           72  + int _ = 0;
           73  +END
           74  +CASE(2)
           75  + int lines_[] = { 1, 2, 4 }
           76  +;
           77  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           78  + int _ = 6;
           79  +END
           80  +CASE(3)
           81  + int lines_[] = { 250, 105, 155, 205, 350 }
           82  +;
           83  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           84  + int _ = 499;
           85  +END
           86  +CASE(4)
           87  +int lines_[] = {0};
           88  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           89  + int _ = 0;
           90  +END
           91  +CASE(5)
           92  +int lines_[] = {1};
           93  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           94  + int _ = 1;
           95  +END
           96  +CASE(5)
           97  + int lines_[] = {10};
           98  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
           99  + int _ = 10;
          100  +END
          101  +CASE(5)
          102  + int lines_[] = {10,10};
          103  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
          104  + int _ = 11;
          105  +END
          106  +CASE(5)
          107  + int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000};
          108  +   vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
          109  + int _ = 1000049;
          110  +END
          111  +
          112  +}
          113  +// END CUT HERE

Added SRM/499-U/1C-U.cpp version [c23044dc81c5002a]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +template<typename V>
           23  +class Graph
           24  +{
           25  + map<V, int> v2id_;
           26  + vector<V>   id2v_;
           27  +public:
           28  + vector< vector<int> > G;
           29  +
           30  + int vert( const V& t )
           31  + {
           32  +  if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); G.resize(G.size()+1); }
           33  +  return v2id_[t];
           34  + }
           35  + void edge( const V& s_, const V& t_ )
           36  + {
           37  +  int s=vert(s_), t=vert(t_);
           38  +  G[s].push_back(t);
           39  + }
           40  + const V& orig( int v )
           41  + {
           42  +  return id2v_[v];
           43  + }
           44  +};
           45  +
           46  +class StronglyConnectedComponent
           47  +{
           48  +public:
           49  + StronglyConnectedComponent( const vector< vector<int> >& G )
           50  +  : scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size()), scc_id(G.size())
           51  + {
           52  +  for(int v=0; v<G.size(); ++v)
           53  +   dfs(v);
           54  + }
           55  +
           56  + vector< vector<int> > scc;    // scc[i] : the list of verts in the i-th component
           57  + vector< vector<int> > forest; // the forest structure over sccs
           58  +
           59  +private:
           60  + const vector< vector<int> >& G;
           61  + int no;
           62  + vector<int> dfs_no; // Special: 0       : not visited yet
           63  + vector<int> dfs_lo; // Special: INT_MAX : already classified into some scc !!!! not a good idea!
           64  + // rather use scc_id for that purpose (distinguishing assigned or not)
           65  + vector<int> scc_id;
           66  + vector<int> pending;
           67  +
           68  + void dfs(int v)
           69  + {
           70  +  if( dfs_no[v] )
           71  +   return;
           72  +
           73  +  dfs_no[v] = dfs_lo[v] = ++no;    // visit v
           74  +  for(int i=0; i<G[v].size(); ++i) // visit children
           75  +  {
           76  +   int u = G[v][i];
           77  +   dfs( u );
           78  +   if( !is_already_classified_in_some_scc(u) )
           79  +    dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] );
           80  +  }
           81  +
           82  +  pending.push_back(v);
           83  +  if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a scc
           84  +   // todo: pending -> dfs_lo:=INT_MAX
           85  +   scc.push_back(pending), pending.clear();
           86  +
           87  +   // construct scc-forest (if needed)
           88  +   scc_id[v] = scc.size()-1;
           89  +   set<int> children;
           90  +   for(int i=0; i<G[v].size(); ++i)
           91  +    if( dfs_lo[G[v][i]] != v )
           92  +     children.insert( scc_id[dfs_lo[G[v][i]]] );
           93  +   forest.push_back( vector<int>(children.begin(), children.end()) );
           94  +  }
           95  + }
           96  +};
           97  +
           98  +
           99  +class ImpossibleGame { public:
          100  + static LL C(LL n, LL k) {
          101  +  LL v = 1;
          102  +  for(int i=1; i<=k; ++i)
          103  +   v = v * (n+1-i) / i;
          104  +  return v;
          105  + }
          106  + static LL weight(LL a, LL b, LL c, LL d) {
          107  +  return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c);
          108  + }
          109  +
          110  + long long getMinimum(int k, vector <string> before, vector <string> after)
          111  + {
          112  +  vector< pair< vector<int>, vector<int> > > dif;
          113  +  for(int i=0; i<after.size(); ++i)
          114  +  {
          115  +   vector<int> be(4), af(4);
          116  +   for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A'] ++;
          117  +   for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A'] ++;
          118  +   dif.push_back( make_pair(be,af) );
          119  +  }
          120  +
          121  +  Graph< vector<int> > G;
          122  +
          123  +  vector<int> v(4);
          124  +  for(v[0]=0; v[0]<=k; ++v[0])
          125  +  for(v[1]=0; v[0]+v[1]<=k; ++v[1])
          126  +  for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2])
          127  +  for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3])
          128  +  {
          129  +   G.vert(v);
          130  +   for(int i=0; i<dif.size(); ++i)
          131  +   {
          132  +    bool dame = false;
          133  +
          134  +    vector<int> u = v;
          135  +    for(int k=0; k<4; ++k)
          136  +    {
          137  +     if( (u[k]-=dif[i].first[k]) < 0 )
          138  +      dame = true;
          139  +     u[k] += dif[i].second[k];
          140  +    }
          141  +    if( !dame )
          142  +     G.edge(v, u);
          143  +   }
          144  +  }
          145  +
          146  +  StronglyConnectedComponent scc(G.G);
          147  +  return 0;
          148  + }
          149  +};
          150  +
          151  +// BEGIN CUT HERE
          152  +#include <ctime>
          153  +double start_time; string timer()
          154  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          155  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          156  + { os << "{ ";
          157  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          158  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          159  +void verify_case(const long long& Expected, const long long& Received) {
          160  + bool ok = (Expected == Received);
          161  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          162  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          163  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          164  +#define END  verify_case(_, ImpossibleGame().getMinimum(k, before, after));}
          165  +int main(){
          166  +
          167  +CASE(0)
          168  + int k = 1;
          169  + string before_[] = { "A" }
          170  +;
          171  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          172  + string after_[] = { "B" }
          173  +;
          174  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          175  + long long _ = 2LL;
          176  +END
          177  +CASE(1)
          178  + int k = 2;
          179  + string before_[] = { "A", "A", "D" }
          180  +;
          181  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          182  + string after_[] = { "B", "C", "D" }
          183  +;
          184  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          185  + long long _ = 5LL;
          186  +END
          187  +CASE(2)
          188  + int k = 2;
          189  + string before_[] = { "B", "C", "D" }
          190  +;
          191  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          192  + string after_[] = { "C", "D", "B" }
          193  +;
          194  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          195  + long long _ = 9LL;
          196  +END
          197  +CASE(3)
          198  + int k = 6;
          199  + string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" }
          200  +;
          201  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          202  + string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" }
          203  +;
          204  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          205  + long long _ = 499LL;
          206  +END
          207  +/*
          208  +CASE(4)
          209  + int k = ;
          210  + string before_[] = ;
          211  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          212  + string after_[] = ;
          213  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          214  + long long _ = LL;
          215  +END
          216  +CASE(5)
          217  + int k = ;
          218  + string before_[] = ;
          219  +   vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
          220  + string after_[] = ;
          221  +   vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
          222  + long long _ = LL;
          223  +END
          224  +*/
          225  +}
          226  +// END CUT HERE

Modified lib/numeric/modArith.cpp from [b348fa4dbce4653d] to [f45d60576bba9894].

     2      2   //-------------------------------------------------------------
     3      3   // Modulo Arithmetics
     4      4   //
     5      5   // Verified by
     6      6   //   - TCO10 R3 LV3
     7      7   //-------------------------------------------------------------
     8      8   
     9         -static const int MODVAL = 1000000007; // op/ depends on primarity of the MODVAL
            9  +static const int MODVAL = 1000000007; // must be prime for op/
    10     10   struct mint
    11     11   {
    12     12    int val;
    13     13    mint():val(0){}
    14     14    mint(int x):val(x%MODVAL) {}
    15     15    mint(LL  x):val(x%MODVAL) {}
    16     16   };
    17         -
    18     17   mint operator+(mint x, mint y) { return x.val+y.val; }
    19     18   mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
    20     19   mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
    21     20   mint POW(mint x, int e) {
    22     21    mint v = 1;
    23     22    for(;e;x=x*x,e>>=1)
    24     23     if(e&1)
    25     24      v=v*x;
    26     25    return v;
    27     26   }
    28     27   mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
    29     28   
    30     29   vector<mint> FAC_(1,1);
    31         -void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); }
           30  +void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); }
    32     31   mint FAC(mint x)       { return FAC_[x.val]; }
    33     32   mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
    34     33   
    35     34   /*
    36     35   // MODVAL must be a prime!!
    37     36   LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
    38     37   {

Deleted lib/numeric/modArithOld.cpp version [b669f317babaf285]

     1         -
     2         -//-------------------------------------------------------------
     3         -// Modulo Arithmetics
     4         -//
     5         -// Verified by
     6         -//   - SRM 397 Div1 LV2
     7         -//   - SRM 428 Div1 LV2
     8         -//   - CodeCraft 2010 CNTINT DRAW
     9         -//-------------------------------------------------------------
    10         -
    11         -static const LL MODVAL = 1000000007; // must fit in 32-bits
    12         -
    13         -LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
    14         -LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
    15         -LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
    16         -LL POW(LL x, LL e) {
    17         - LL v = 1;
    18         - for(;e;x=MUL(x,x),e>>=1)
    19         -  if(e&1)
    20         -   v = MUL(v, x);
    21         - return v;
    22         -}
    23         -
    24         -// MODVAL must be a prime!!
    25         -LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); }
    26         -
    27         -// MODVAL must be a prime!!
    28         -LL C(LL n, LL k) {
    29         - LL v = 1;
    30         - for(LL i=1; i<=k; ++i)
    31         -  v = DIV(MUL(v, n-i+1), i);
    32         - return v;
    33         -}
    34         -
    35         -// MODVAL must be a prime!!
    36         -LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
    37         -{
    38         - if( b >  e ) return 0;
    39         - if( k <= 1 ) return k*(e-b+1);
    40         - return DIV(SUB(POW(k, e+1), POW(k,b)), k-1);
    41         -}
    42         -
    43         -
    44         -
    45         -
    46         -LL Cpascal(LL n, LL k)
    47         -{
    48         - vector< vector<LL> > c(n+1, vector<LL>(k+1));
    49         - for(LL nn=1; nn<=n; ++nn)
    50         -  for(LL kk=0; kk<=min(nn,k); ++kk)
    51         -   c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[nn-1][kk]);
    52         - return c[n][k];
    53         -}
    54         -
    55         -vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b)
    56         -{
    57         -   int N = a.size();
    58         -   vector< vector<LL> > c(N, vector<LL>(N));
    59         -   for(int i=0; i<N; ++i)
    60         -   for(int j=0; j<N; ++j)
    61         -   for(int k=0; k<N; ++k)
    62         -      c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j]));
    63         -   return c;
    64         -}
    65         -
    66         -// works for non-prime MODVAL
    67         -LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1
    68         -{
    69         -   vector< vector<LL> > v(2, vector<LL>(2));
    70         -   vector< vector<LL> > x(2, vector<LL>(2));
    71         -   v[0][0] = v[1][1] = 1;
    72         -   x[0][0] = x_; x[0][1] = 0;
    73         -   x[1][0] = 1 ; x[1][1] = 1;
    74         -   for(;e;x=MATMUL(x,x),e>>=1)
    75         -      if(e&1)
    76         -         v = MATMUL(v, x);
    77         -   return v[1][0];
    78         -}
    79         -
    80         -// works for non-prime MODVAL
    81         -LL HYP(LL x_, LL e) // e x^0 + (e-1) x^1 + ... + 1 x^e-1 = GEO(x,1)+GEO(x,2)+...+GEO(x,e)
    82         -{
    83         -   vector< vector<LL> > v(3, vector<LL>(3));
    84         -   vector< vector<LL> > x(3, vector<LL>(3));
    85         -   v[0][0] = v[1][1] = v[2][2] = 1;
    86         -   x[0][0] = x_; x[0][1] = 0; x[0][2] = 0;
    87         -   x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0;
    88         -   x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1;
    89         -   e++;
    90         -   for(;e;x=MATMUL(x,x),e>>=1)
    91         -      if(e&1)
    92         -         v = MATMUL(v, x);
    93         -   return v[2][0];
    94         -}