結果

問題 No.1086 桁和の桁和2
コンテスト
ユーザー yukudo
提出日時 2020-06-19 23:49:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 157 ms / 3,000 ms
コード長 2,435 bytes
コンパイル時間 2,051 ms
コンパイル使用メモリ 171,536 KB
実行使用メモリ 14,480 KB
最終ジャッジ日時 2024-07-22 17:57:59
合計ジャッジ時間 6,350 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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;

ll mod_pow(ll a, ll b, ll p) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

ll mod_inv(ll a, ll p) {
  return mod_pow(a % p, p - 2, p);
}



ll ways(ll n) {
  ll res = mod_pow(10, n, MOD);
  res = (res - 1 + MOD) % MOD;
  res *= mod_inv(9, MOD);
  res %= MOD;
  return res;
}

vector<ll> ways(ll L, ll R) {
  ll l = ways(L);
  ll r = ways(R);
  vector<ll> 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++) {
      if (dp[i][j] == 0) continue;
      for (int k = 0; k < 10; k++) {
        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 = 2;
//   int R = 4;
//   {
//     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