結果

問題 No.1086 桁和の桁和2
コンテスト
ユーザー yukudo
提出日時 2020-06-19 23:22:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,730 bytes
コンパイル時間 1,874 ms
コンパイル使用メモリ 177,488 KB
実行使用メモリ 21,228 KB
最終ジャッジ日時 2024-07-03 15:47:57
合計ジャッジ時間 7,103 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


const ll MOD = ((ll)1e9)+7;

#define SZ(v) ((int)(v).size())
using Array = vector<ll>;
using Matrix = vector<Array>;

Matrix zero(int N){ return Matrix(N, Array(N)); }

Matrix identity(int N) {
  Matrix A = zero(N);
  REP(i, N) A[i][i] = 1;
  return A;
}

Matrix add(const Matrix &A, const Matrix& B){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) {
    C[i][j] += A[i][j] + B[i][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

Array mul(const Matrix &A, const Array &x){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Array y(N);
  REP(i, N) REP(j, M)
    y[i] += A[i][j] * x[j];
  return y;
}

// A:[N,P] * B:[P,M] = C:[N,M]
Matrix mul(const Matrix &A, const Matrix& B) {
  const int N = SZ(A);
  const int P = SZ(A[0]);
  const int M = SZ(B[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) REP(k, P) {
    C[i][j] += A[i][k] * B[k][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

// O ( n^3 log e )
// Matrix pow(const Matrix& A, ll e) {
//   return e == 0 ? identity(SZ(A)) :
//     e % 2 == 0 ? pow( mul(A,A) , e/2 ) : mul(A, pow(A,e-1));
// }
Matrix pow(Matrix A, ll b) {
  Matrix C = identity(SZ(A));
  while (b > 0) {
    if ((b & 1) == 1) C = mul(C, A);
    A = mul(A, A);
    b >>= 1;
  }
  return C;
}

void print(const Matrix& A){
  REP(i, SZ(A)){
    REP(j, SZ(A[0])){
      cout << A[i][j] << " ";
    }
    cout << endl;
  }
  cout << "---------------------" << endl;
}



ll ways(ll n) {

  Matrix A = zero(4);
  A[0][0] = 10;
  A[0][1] = 1;
  A[1][1] = 1;

  Array b(2);
  b[0] = 1;
  b[1] = 1;

  if (n == 0) {
    return 0;
  }

  A = pow(A, n-1);
  b = mul(A, b);
  return b[0];
}

Array ways(ll L, ll R) {
  ll l = ways(L);
  ll r = ways(R);
  Array w(10);
  for (int i = 1; i <= 9; i++) w[i] = ((r - l) % MOD + MOD) % MOD;
  w[0] = 1;
  return w;
}

const int MAX_N = 112345;
ll dp[MAX_N][10];

int main2() {

  CLR(dp, 0);


  int N = nextLong();
  vector<ll> L(N), R(N), D(N);
  REP(i, N) L[i] = nextLong();
  REP(i, N) R[i] = nextLong();
  REP(i, N) D[i] = nextLong();

  dp[0][0] = 1;
  for (int i = 0; i < N; i++) {
    auto w = ways(L[i], R[i]);
    // cout << "w="; pv(ALL(w));
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < 10; k++) {
      if (dp[i][j] == 0) continue;
        int nj = (j + k) % 9;
        if (nj == 0) {
          if (j == 0 && k == 0) nj = 0; else nj = 9;
        }
        (dp[i+1][nj] += (dp[i][j] * w[k]) % MOD) %= MOD;
      }
    }
    // for (int j = 0; j < 10; j++) {cout << dp[i+1][j] << " "; } cout << endl;
    for (int j = 0; j < 10; j++) {
      if (D[i] != j)
        dp[i+1][j] = 0;
    }

  }

  ll ans = 0;
  for (int j = 0; j < 10; j++){
    ans += dp[N][j];
  }
  cout << ans << endl;
  return 0;
}

int main() {

//   int L = 1;
//   int R = 2;
//   {
//     vector<int> v(10);
//     v[0] = 1;
//     for (int i = pow(10, L); i < pow(10, R); i++) {
//       int r = i % 9;
//       if (r == 0) r = 9;
//       ++v[r];
//     }
//     pv(ALL(v));
//   }

//   auto x = ways(L, R);
//   pv(ALL(x));
// return 0;

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}
0