Artifact f7d0e00a6c0eeef7f45a83cac6fc4494424bc0c1

• File SRM/444/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

static const LL MODVAL = 1000000007;
typedef vector< vector<LL> > matrix;

vector<LL> vMul( const matrix& A, const vector<LL>& B )
{
  const int n = A.size();

  vector<LL> C(n);
  for(int i=0; i<n; ++i)
    for(int j=0; j<n; ++j)
      C[i] = (C[i] + A[i][j] * B[j]) % MODVAL;
  return C;
}

matrix mMul( const matrix& A, const matrix& B )
{
  const int n = A.size();

  matrix C(n, vector<LL>(n));
  for(int i=0; i<n; ++i)
    for(int j=0; j<n; ++j) {
      LL Cij = 0;
      for(int k=0; k<n; ++k)
        Cij = (Cij + A[i][k] * B[k][j]) % MODVAL;
      C[i][j] = Cij;
    }
  return C;
}

matrix mPow( matrix M, LL t ) // t>0
{
  matrix R;
  for(; t; t>>=1, M=mMul(M,M))
    if( t&1 )
      R = (R.empty() ? M : mMul(R,M));
  return R;
}

LL GCD(LL a, LL b) { while(a) swap(b%=a,a); return b; }
LL LCM(LL a, LL b) { return a/GCD(a,b)*b; }

class AvoidFour { public:
  int count(long long n) 
  {
    matrix A(6, vector<LL>(6));
    A[1][0] = 8; A[1][1] = 9; A[1][2] = 9; A[1][3] = 9; A[1][4] = 9;
    A[2][0] = 1; A[2][1] = 1;
                              A[3][2] = 1;
                                           A[4][3] = 1;
                 A[5][1] = 1; A[5][2] = 1; A[5][3] = 1; A[5][4] = 1; A[5][5] = 1;

    vector<LL> v(6);
    v[0] = 1;


    vector<LL> fours;
    for(LL f=44; f<=n; f=f*10+4)
      fours.push_back(f);
    int N = fours.size();

    LL total = 0;
    for(int m=0; m<(1<<N); ++m)
    {
      LL lcm=1, bitCnt=0;
      for(int i=0; (1<<i)<=m; ++i)
        if( m & (1<<i) ) {
          lcm = LCM(lcm, fours[i]);
          if( lcm > n )
            break;
          bitCnt ++;
        }
      if( lcm <= n ) {
        matrix Af = mPow(A, lcm);
        Af[5] = A[5];

        LL sub = vMul(mMul(A,mPow(Af,n/lcm)), v)[5];
        total = (bitCnt&1 ? total-sub+MODVAL : total+sub) % MODVAL;
      }
    }
    return total;
  }
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END   verify_case(_, AvoidFour().count(n));}
int main(){

CASE(0)
  long long n = 4LL; 
  int _ = 9998; 
END
CASE(1)
  long long n = 5LL; 
  int _ = 99980; 
END
CASE(2)
  long long n = 87LL; 
  int _ = 576334228; 
END
CASE(3)
  long long n = 88LL; 
  int _ = 576334228; 
END
CASE(4)
  long long n = 4128LL; 
  int _ = 547731225; 
END

}
// END CUT HERE