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

Added SRM/550-U/1C.cpp version [b366e6f6edd62cdd]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +static const int MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {}
           28  + mint(size_t 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 = LL(x.val)*y.val; }
           33  +mint operator+(mint x, mint y) { return x+=y; }
           34  +mint operator*(mint x, mint y) { return x*=y; }
           35  +
           36  +template<typename T>
           37  +vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v)
           38  +{
           39  + int N = a.size();
           40  + vector<T> u(N);
           41  + for(int i=0; i<N; ++i)
           42  + for(int j=0; j<N; ++j)
           43  +  u[i] += a[i][j]*v[j];
           44  + return u;
           45  +}
           46  +
           47  +template<typename T>
           48  +vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b)
           49  +{
           50  + int N = a.size();
           51  + vector< vector<T> > c(N, vector<T>(N));
           52  + for(int i=0; i<N; ++i)
           53  + for(int j=0; j<N; ++j)
           54  + for(int k=0; k<N; ++k)
           55  +  c[i][j] += a[i][k]*b[k][j];
           56  + return c;
           57  +}
           58  +
           59  +template<typename T>
           60  +vector< vector<T> > MATPOW(vector< vector<T> > a, LL e)
           61  +{
           62  + int N = a.size();
           63  + vector< vector<T> > c(N, vector<T>(N));
           64  + for(int i=0; i<N; ++i) c[i][i] = 1;
           65  + for(; e; e>>=1) {
           66  +  if(e&1)
           67  +   c = MATMUL(c, a);
           68  +  a = MATMUL(a, a);
           69  + }
           70  + return c;
           71  +}
           72  +
           73  +class ConversionMachine { public:
           74  + int countAll(string word1, string word2, vector <int> costs, int maxCost)
           75  + {
           76  +  int d[3] = {};
           77  +  LL minCost = 0;
           78  +  for(int i=0; i<word1.size(); ++i) {
           79  +   int dd=0;
           80  +   while( word1[i] != word2[i] ) {
           81  +    dd      += 1;
           82  +    minCost += costs[word1[i]-'a'];
           83  +    word1[i] = (word1[i]+1-'a')%3 + 'a';
           84  +   }
           85  +   d[dd] += 1;
           86  +  }
           87  +
           88  +  if( minCost > maxCost )
           89  +   return 0;
           90  +  LL c3 = accumulate(costs.begin(), costs.end(), 0LL);
           91  +  return solve(d, (maxCost-minCost)/c3*3+d[1]*1+d[2]*2).val;
           92  + }
           93  +
           94  + mint solve(int d[3], int rem)
           95  + {
           96  +  int n = d[0]+d[1]+d[2];
           97  +
           98  +  map<pair<int,int>, int> enc;
           99  +  for(int b=0,id=0; b<=n; ++b)
          100  +  for(int c=0; b+c<=n; ++c,++id)
          101  +   enc[make_pair(b,c)] = id;
          102  +  int D = enc.size();
          103  +
          104  +  vector< vector<mint> > M(D+1, vector<mint>(D+1));
          105  +  for(int b=0; b<=n; ++b)
          106  +  for(int c=0; b+c<=n; ++c)
          107  +  {
          108  +   int a = n-b-c;
          109  +   if(a) {
          110  +    M[enc[make_pair(b,c+1)]][enc[make_pair(b,c)]] = a;
          111  +   }
          112  +   if(b) {
          113  +    M[enc[make_pair(b-1,c)]][enc[make_pair(b,c)]] = b;
          114  +    if(b-1==0 && c==0)
          115  +     M.back()[enc[make_pair(b,c)]] = b;
          116  +   }
          117  +   if(c) {
          118  +    M[enc[make_pair(b+1,c-1)]][enc[make_pair(b,c)]] = c;
          119  +   }
          120  +  }
          121  +  M.back().back() = 1;
          122  +
          123  +  vector<mint> V(D+1);
          124  +  V[enc[make_pair(d[1],d[2])]] = 1;
          125  +  V.back() = V[0];
          126  +
          127  +  return MATMUL(MATPOW(M, rem), V).back();
          128  + }
          129  +};
          130  +
          131  +// BEGIN CUT HERE
          132  +#include <ctime>
          133  +double start_time; string timer()
          134  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          135  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          136  + { os << "{ ";
          137  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          138  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          139  +void verify_case(const int& Expected, const int& Received) {
          140  + bool ok = (Expected == Received);
          141  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          142  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          143  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          144  +#define END  verify_case(_, ConversionMachine().countAll(word1, word2, costs, maxCost));}
          145  +int main(){
          146  +
          147  +CASE(0)
          148  + string word1 = "a";
          149  + string word2 = "b";
          150  + int costs_[] = {100,2,3};
          151  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          152  + int maxCost = 205;
          153  + int _ = 2;
          154  +END
          155  +CASE(1)
          156  + string word1 = "abcba";
          157  + string word2 = "abcba";
          158  + int costs_[] = {67,23,43};
          159  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          160  + int maxCost = 0;
          161  + int _ = 1;
          162  +END
          163  +CASE(2)
          164  + string word1 = "cccccccc";
          165  + string word2 = "aaaaaaaa";
          166  + int costs_[] = {10000000,1,1};
          167  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          168  + int maxCost = 100;
          169  + int _ = 40320;
          170  +END
          171  +CASE(3)
          172  + string word1 = "aa";
          173  + string word2 = "cc";
          174  + int costs_[] = {1,10,100};
          175  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          176  + int maxCost = 1787;
          177  + int _ = 123611681;
          178  +END
          179  +/*
          180  +CASE(4)
          181  + string word1 = ;
          182  + string word2 = ;
          183  + int costs_[] = ;
          184  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          185  + int maxCost = ;
          186  + int _ = ;
          187  +END
          188  +CASE(5)
          189  + string word1 = ;
          190  + string word2 = ;
          191  + int costs_[] = ;
          192  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
          193  + int maxCost = ;
          194  + int _ = ;
          195  +END
          196  +*/
          197  +}
          198  +// END CUT HERE

Modified lib/numeric/modArith.cpp from [e5662c451b84a185] to [4e73ce5907de5c44].

    34     34     int nn = CP_.size();
    35     35     CP_.push_back(vector<mint>(nn+1,1));
    36     36     for(int kk=1; kk<nn; ++kk)
    37     37      CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
    38     38    }
    39     39    return k<0 || n<k ? 0 : CP_[n][k];
    40     40   }
           41  +
           42  +template<typename T>
           43  +vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v)
           44  +{
           45  + int N = a.size();
           46  + vector<T> u(N);
           47  + for(int i=0; i<N; ++i)
           48  + for(int j=0; j<N; ++j)
           49  +  u[i] += a[i][j]*v[j];
           50  + return u;
           51  +}
           52  +
           53  +template<typename T>
           54  +vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b)
           55  +{
           56  + int N = a.size();
           57  + vector< vector<T> > c(N, vector<T>(N));
           58  + for(int i=0; i<N; ++i)
           59  + for(int j=0; j<N; ++j)
           60  + for(int k=0; k<N; ++k)
           61  +  c[i][j] += a[i][k]*b[k][j];
           62  + return c;
           63  +}
           64  +
           65  +template<typename T>
           66  +vector< vector<T> > MATPOW(vector< vector<T> > a, LL e)
           67  +{
           68  + int N = a.size();
           69  + vector< vector<T> > c(N, vector<T>(N));
           70  + for(int i=0; i<N; ++i) c[i][i] = 1;
           71  + for(; e; e>>=1) {
           72  +  if(e&1)
           73  +   c = MATMUL(c, a);
           74  +  a = MATMUL(a, a);
           75  + }
           76  + return c;
           77  +}
    41     78   
    42     79   /*
    43     80   // MODVAL must be a prime!!
    44     81   LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
    45     82   {
    46     83    if( b >  e ) return 0;
    47     84    if( k <= 1 ) return k*(e-b+1);
    48     85    return DIV(SUB(POW(k, e+1), POW(k,b)), k-1);
    49     86   }
    50     87   
    51         -LL Cpascal(LL n, LL k)
    52         -{
    53         - vector< vector<LL> > c(n+1, vector<LL>(k+1));
    54         - for(LL nn=1; nn<=n; ++nn)
    55         -  for(LL kk=0; kk<=min(nn,k); ++kk)
    56         -   c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[nn-1][kk]);
    57         - return c[n][k];
    58         -}
    59         -
    60         -vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b)
    61         -{
    62         -   int N = a.size();
    63         -   vector< vector<LL> > c(N, vector<LL>(N));
    64         -   for(int i=0; i<N; ++i)
    65         -   for(int j=0; j<N; ++j)
    66         -   for(int k=0; k<N; ++k)
    67         -      c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j]));
    68         -   return c;
    69         -}
    70         -
    71     88   // works for non-prime MODVAL
    72     89   LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1
    73     90   {
    74     91      vector< vector<LL> > v(2, vector<LL>(2));
    75     92      vector< vector<LL> > x(2, vector<LL>(2));
    76     93      v[0][0] = v[1][1] = 1;
    77     94      x[0][0] = x_; x[0][1] = 0;