cafelier@SRM

SRM444 1000

あとで | 23:05 |

大筋ではあってた。ひたすら行列のべき乗。

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;
  }
};

初期状態(k=0桁の場合)

(1) ... k桁の自然数のうち、0桁のものの数 (k=0のときだけ1)
(0) ... k桁の自然数のうち、最後に4がゼロ連続
(0) ... k桁の自然数のうち、最後に4が1連続
(0) ... k桁の自然数のうち、最後に4が2連続
(0) ... k桁の自然数のうち、最後に4が3連続
(0) ... k桁未満の自然数のうち、4が4連続してないもの

というベクトル v に

(0 0 0 0 0 0)
(8 9 9 9 9 0)
(1 1 0 0 0 0)
(0 0 1 0 0 0)
(0 0 0 1 0 0)
(0 1 1 1 1 1)

という行列 A を左から掛けてあげると、k=1桁の場合、k=2桁の場合、...が求まっていく。左端の列がk=0→1の時に"0"を入れないための特殊処理。それ以外の時は4以外の9種類のどの数字を入れても「最後に4がゼロ連続」になるので9 9 9 9。「最後に4が1連続」になるのは「ゼロ連続」状態に4を足したとき。……という遷移行列。

• なので、44...44の倍数桁のを除く、という条件を無視すれば、答えは A^{n+1} v の最後の成分。
  • ここから44の倍数桁のものを除くには、(A^44)^{n/44+1} v の最後の成分を引いてやればよい。
  • 444の倍数桁のものを除くには、(A^444)^{n/444+1} v の最後の成分を引いてやればよい。
  • 以下同様
  • これだと44と444の公倍数を引きすぎるので、
    • (A^LCM(44,444))^{n/LCM(44,444)+1} v の分は足しておく
    • というような足したり引いたりを包除原理で調整
• n<=4e10なので、せいぜい9通りの例外ケースに対する包除原理なので2^9=512回くらい行列べき乗をやればよい。

• 6*6*2^9*log(n) くらいなので時間的には余裕