ferinの競プロ帳

競プロについてのメモ

ARC096 D - Static Sushi

問題ページ
D - Static Sushi

考えたこと

  • 何か既視感を感じる
  • どうせ引き返すのは高々1回
  • 時計回り or 反時計回りに一方向に回るだけならO(N)で簡単に求まる
  • dp1[i] = ([0,i]で得られる最大のカロリー、時計回り)
  • dp2[i] = ([i,n-1]で得られる最大のカロリー、反時計回り) とする
  • dp1[i] まで行った後に引き返すなら [i+1,n-1]で得られる最大のカロリーまで行くのが最善
  • 反時計回り側で得られるカロリーはdp2[i+1]を見ればわかる
  • dp2[i] まで行った後に引き返すときも同様にO(1)で求まる
  • したがってO(N)で解ける

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  VI x(n), v(n);
  REP(i, n) cin >> x[i] >> v[i];

  VI dp1(n);
  dp1[0] = v[0] - x[0];
  FOR(i, 1, n) dp1[i] = dp1[i-1] + v[i] - (x[i] - x[i-1]);
  FOR(i, 1, n) chmax(dp1[i], dp1[i-1]);

  VI dp2(n);
  dp2[n-1] = v[n-1] - (c - x[n-1]);
  for(int i=n-2; i>=0; --i) {
    dp2[i] = dp2[i+1] + v[i] - (x[i+1] - x[i]);
  }
  for(int i=n-2; i>=0; --i) {
    dp2[i] = max(dp2[i], dp2[i+1]);
  }

  int ans = max(0LL, dp2[0]);
  REP(i, n) {
    // i番目まで時計回りで取る
    int tmp = dp1[i];
    // [i+1, n-1] の最大
    if(i+1<n && dp2[i+1] - x[i] > 0) tmp += dp2[i+1] - x[i];
    chmax(ans, tmp);
  }
  for(int i=n-1; i>=0; --i) {
    int tmp = dp2[i];
    if(i >= 1 && dp1[i-1] - (c - x[i]) > 0 ) tmp += dp1[i-1] - (c - x[i]);
    chmax(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}

ARC096 C - Half and Half

問題ページ
C - Half and Half

考えたこと

  • 頑張って数学O(1)もありそうだけど絶対つらい
  • 制約を見ると10^5なのでO(max(X,Y))できる
  • ABピザを2i枚使ったとするとAピザ、Bピザの枚数は一意に定まる
  • 全探索をする

ソースコード

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;

  int ans = LLINF;
  REP(i, max(x, y)+1) {
    // i*2枚をAB pizza
    int tmp = i*c*2;
    if(x > i) tmp += (x-i)*a;
    if(y > i) tmp += (y-i)*b;
    chmin(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}

ARC035 C - アットコーダー王国の交通事情

問題ページ
C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder

考えたこと

  • Sを求めるには全点対の最短距離が必要
  • ワーシャルフロイドをしたい
  • 辺を追加するクエリの度にワーシャルフロイドしてO(N^3)かけていたらO(N^3K)でまず通らない
  • グラフ中で高々1本しか辺が増えないのに全頂点に対して最短距離を計算するのは無駄そう
  • 頂点x,yに辺を追加するとき、頂点集合G={i|i∉x,y}に対する最短距離はすでに求まっている
  • したがってワーシャルフロイドで中間として通る点として考えるのはx,yのいずれかのみでよい
  • 辺の追加1回ごとにO(N^2)しかかからない
  • 合計でO(N^2K)でこれなら通る

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }

int d[405][405];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  REP(i, n) REP(j, n) d[i][j] = i==j?0:INF;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    d[a][b] = d[b][a] = c;
  }

  REP(k, n) REP(i, n) REP(j, n) chmin(d[i][j], d[i][k]+d[k][j]);
  int all = 0;
  REP(i, n) REP(j, n) if(d[i][j]!=INF) all += d[i][j];

  int K;
  cin >> K;
  REP(_, K) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    if(d[a][b] < c) {
      cout << all/2 << endl;
      continue;
    }
    d[a][b] = d[b][a] = c;
    // 頂点aを中間地点とするとき
    REP(i, n) REP(j, n) chmin(d[i][j], d[i][a]+d[a][j]);
    // 頂点bを中間地点とするとき
    REP(i, n) REP(j, n) chmin(d[i][j], d[i][b]+d[b][j]);
    all = 0;
    REP(i, n) REP(j, n) if(d[i][j]!=INF) all += d[i][j];
    cout << all/2 << endl;
  }

  return 0;
}

AOJ2510 双子の読書感想文

問題ページ
Twin book report | Aizu Online Judge

考えたこと

  • まず本を読む時間を最小化することを考える
  • 感想を書く時間を無視して読書にかかる時間の方だけ考える
  • とりあえずソートしたい気持ちになる
  • いろいろ試してると大体 sum(r) で読書が終わりそう
  • sum(r)でできないのはsampleのように max(r) > sum(r) - max(r) となるときだけっぽい
  • rを降順ソートしたとする
  • max(r) <= sum(r)-max(r) ならば 亜美がr[0],r[1],…,r[n-1]、真美がr[1],r[2],…,r[n-1],r[0]と読めばsum(r)で読書ができる
  • max(r) > sum(r)-max(r) ならば 問題文中のサンプルのようにmax(r)の本を読んでいる間に残りの本を全部読むとしてmax(r)*2となる
  • 感想を書く時間について考える
  • max(r) <= sum(r)-max(r) ならば sum(r) で読書が完了しているので sum(w) で感想を書けばよくこれが最適解
  • max(r) > sum(r)-max(r) ならば問題文中のサンプルのように読書中の空いた時間に感想を書いておきたい
  • したがってmax(r)*2 + sum(w) - (読書中に感想を書いた分) になる
  • 読書中に感想を書ける時間は max(r)*2 - sum(r) が最大
  • 最大にできるだけ近づけられるようなwの部分集合の取り方を知りたい
  • これは部分和DPをすれば求まる
  • O(nsum(w))の状態を取るとだめだが冷静に考えると部分和の最大はO(max(r))なのでO(nmax(r))で求められる

解法

max(r) <= sum(r)-max(r) ならば sum(r) + sum(w)
max(r) > sum(r)-max(r) ならば max(r)*2 + sum(w) - (部分和DPで求めた値)
部分和DPはO(nmax(r))でできる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dp[1010][3010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VI r(n), w(n);
    int sumr = 0, sumw = 0;
    int ma=0, idx=-1;
    REP(i, n) {
      cin >> r[i] >> w[i];
      if(ma < r[i]) {
        ma = r[i];
        idx = i;
      }
      sumr += r[i];
      sumw += w[i];
    }

    if(ma <= sumr - ma) {
      cout << sumr + sumw << endl;
    } else {
      memset(dp, 0, sizeof(dp));
      dp[0][0] = 1;
      REP(i, n) REP(j, 2*ma-sumr+1) {
        dp[i+1][j] |= dp[i][j];
        if(j+w[i] <= 2*ma-sumr && i != idx) dp[i+1][j+w[i]] |= dp[i][j];
      }

      int tmp = -1;
      REP(i, 2*ma-sumr+1) if(dp[n][i]==1) chmax(tmp, i);

      cout << ma*2 + sumw - tmp << endl;
    }
  }

  return 0;
}

AOJ1318 long distance taxi

問題ページ
Long Distance Taxi | Aizu Online Judge

解法

拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。
d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。

入力が面倒だったり10km/Lだったり面倒だけど典型的な拡張dijkstra

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> g[6010];
int d[6010][2010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, cap;
    cin >> n >> m >> cap; cap *= 10;
    if(!n) break;
    string src, dst;
    cin >> src >> dst;
    int V = 0;
    map<string,int> mp;
    REP(i, 6010) g[i].clear();
    REP(i, n) {
      int l;
      string s, t;
      cin >> s >> t >> l;
      if(mp.find(s) == mp.end()) {
        mp[s] = V++;
      }
      if(mp.find(t) == mp.end()) {
        mp[t] = V++;
      }
      g[mp[s]].PB({mp[t], l});
      g[mp[t]].PB({mp[s], l});
      // cout << mp[s] << " " << mp[t] << " " << l << endl;
    }
    VI exist(V, 0);
    REP(i, m) {
      string s;
      cin >> s;
      exist[mp[s]] = 1;
    }
    int start = mp[src], goal = mp[dst];
    // cout << V << endl;

    REP(i, V) REP(j, cap+1) d[i][j] = LLINF;
    d[start][cap] = 0;
    priority_queue<VI, VVI, greater<VI>> que;
    que.push({d[start][cap], start, cap});

    while(que.size()) {
      VI v = que.top(); que.pop();
      // cout << v << endl;
      int dist = v[0], place = v[1], gas = v[2];
      if(dist > d[place][gas]) continue;
      for(PII &p: g[place]) {
        int rest = exist[p.first]?cap:gas-p.second;
        if(gas >= p.second && d[p.first][rest] > d[place][gas] + p.second) {
          d[p.first][rest] = d[place][gas] + p.second;
          que.push({d[p.first][rest], p.first, rest});
        }
      }
    }

    int ans = LLINF;
    REP(i, cap+1) chmin(ans, d[goal][i]);
    if(ans==LLINF) cout << -1 << endl;
    else cout << ans << endl;
  }

  return 0;
}

AOJ0343 プログラミングコンテスト II

問題ページ
Programming Contest II | Aizu Online Judge

解法

(点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧してBIT上での二分探索を用いることでできる。

k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita
pb_ds木について
BITについて
類題

ソースコード

平衡二分探索木

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<typename T>
using btree = tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  btree<PII> tr;
  FOR(i, 1, n+1) tr.insert({0, -i});
  REP(i, c) {
    int type;
    cin >> type;
    if(type == 0) {
      ll t, p; cin >> t >> p;
      tr.erase({sc[t], -t});
      sc[t] += p;
      tr.insert({sc[t], -t});
    } else {
      ll m; cin >> m; m--;
      cout << -tr.find_by_order(m)->second << " " << tr.find_by_order(m)->first << endl;
    }
  }

  return 0;
}

BIT

#include <bits/stdc++.h>
using ll = long long int;
using namespace std;

// Binary Indexed Tree
// 0-indexed
template <typename T>
struct BIT {
  vector<T> bit;
  int neutral = 0, n;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
                   g = [](const T l, const T r) -> T { return l+r; };

  // 初期化
  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_ = 1e5) { n = n_+1; bit.assign(n_+1, neutral); }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < n; x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i)に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
  // 合計がw以上の最小の位置 O(log^2 n)
  int lower_bound(T w) {
    int lb = -1, ub = n;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(query(mid) >= w) ub = mid;
      else lb = mid;
    }
    return ub;
  }
};

ll type[100010], a[100010], b[100010], sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  vector<pair<ll,ll>> v;
  for(int i=0; i<c; ++i) {
    cin >> type[i];
    if(type[i] == 0) {
      cin >> a[i] >> b[i];
      sc[a[i]] += b[i];
      v.push_back({sc[a[i]], -a[i]});
    } else {
      cin >> a[i];
    }
  }

  // (点数、チーム番号)のpairを番号つける
  for(int i=1; i<=n; ++i) v.push_back({0, -i});
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  reverse(v.begin(), v.end());

  map<pair<ll,ll>,ll> p2n;
  vector<pair<ll,ll>> n2p;
  int idx = 0;
  for(auto i: v) {
    p2n[i] = idx++;
    n2p.push_back(i);
  }

  BIT<ll> bit(n2p.size());
  for(int i=1; i<=n; ++i) bit.update(p2n[{0, -i}], 1);

  memset(sc, 0, sizeof(sc));
  for(int i=0; i<c; ++i) {
    if(type[i] == 0) {
      bit.update(p2n[{sc[a[i]], -a[i]}], -1);
      sc[a[i]] += b[i];
      bit.update(p2n[{sc[a[i]], -a[i]}], 1);
    } else {
      int ret = bit.lower_bound(a[i]);
      cout << -n2p[ret].second << " " << n2p[ret].first << endl;
    }
  }

  return 0;
}

AOJ0570 ジグザグ数

問題ページ
ジグザグ数 | Aizu Online Judge

考えたこと

  • 桁DPなのは知ってたので桁DPを考える
  • dp[i桁目][B以下が確定か][mod M][最後に選んだ数][ジグザグ数になってないか上昇か下降か] を書く
  • mod Mを上の桁から取るのが面倒そうだけどよくよく考えると mo[i] = 10^i mod m を前計算しておけばいいだけ
  • 最後の数と比較して上昇か下降かを調べることで最後のフラグがどうなってるか
  • 与えられたA、Bが1桁の場合上昇も下降もないので別に場合分けする
  • Aより大きいではなくA以上なので ans(B以下) - ans(A以下) とするとだめ
  • 10^500とか飛んでくるのでA-1を計算するのも面倒
  • Aがジグザグ数かつmの倍数なら答えに+1することにする
  • 実装するとサンプルで落ちる
  • leading-zeroで057みたいなのを上昇→上昇と判定している
  • dp配列にleading-zeroか判定するフラグを一次元増やす
  • 0ならまだleading-zero、1なら1桁目、2なら2桁目以降なことを表す
  • 投げると通る

実装がたいへん

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

const int MOD = 10000;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dp[505][2][505][10][3][3];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string a, b;
  int m;
  cin >> a >> b >> m;

  int n = b.size();
  if(n != 1) {
    VI mo(n); mo[0] = 1%m;
    FOR(i, 1, n) mo[i] = mo[i-1]*10%m;
    // B以下の数を求める桁DP
    dp[0][0][0][0][0][0] = 1;
    REP(i, n) REP(j, 2) REP(k, m) REP(l, 10) REP(x, 3) REP(y, 3) {
      if(!dp[i][j][k][l][x][y]) continue;
      // cout << i << "," << j << "," << k << "," << l << "," << x << "," << y << " ";
      // cout << dp[i][j][k][l][x][y] << endl;
      int lim = j?9:b[i]-'0';
      REP(d, lim+1) {
        // 上昇か下降か
        int cond = 0;
        if(y==1) {
          if(l < d) cond = 1;
          else if(l > d) cond = 2;
        } else if(x == 1) {
          if(l > d) cond = 2;
        } else if(x == 2) {
          if(l < d) cond = 1;
        }
        // leading-zero
        int cond2 = 0;
        if(y==0) {
          if(d) cond2 = 1;
        } else if(y==1) {
          cond2 = 2;
        } else {
          cond2 = 2;
        }
        (dp[i+1][j||d<lim][(k+mo[n-1-i]*d)%m][d][cond][cond2] += dp[i][j][k][l][x][y]) %= MOD;
      }
    }
  }

  int ans = 0;
  if(n != 1) {
    REP(i, 2) REP(j, 10) FOR(k, 1, 3) REP(l, 3) {
      if(!dp[n][i][0][j][k][l]) continue;
      // cout << n << "," << i << "," << 0 << "," << j << "," << k << "," << l << " ";
      // cout << dp[n][i][0][j][k][l] << endl;
      (ans += dp[n][i][0][j][k][l]) %= MOD;
    }
    REP(i, 9) {
      ans += (i+1)%m==0;
    }
  } else {
    REP(i, b[0]-'0') {
      ans += (i+1)%m==0;
    }
  }

  // cout << ans << endl;

  n = a.size();
  if(n != 1) {
    VI mo(n); mo[0] = 1%m;
    FOR(i, 1, n) mo[i] = mo[i-1]*10%m;
    // A以下の数を求める桁DP
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0][0][0] = 1;
    REP(i, n) REP(j, 2) REP(k, m) REP(l, 10) REP(x, 3) REP(y, 3) {
      if(!dp[i][j][k][l][x][y]) continue;
      // cout << i << "," << j << "," << k << "," << l << "," << x << "," << y << " ";
      // cout << dp[i][j][k][l][x][y] << endl;
      int lim = j?9:a[i]-'0';
      REP(d, lim+1) {
        int cond = 0;
        if(y==1) {
          if(l < d) cond = 1;
          else if(l > d) cond = 2;
        } else if(x == 1) {
          if(l > d) cond = 2;
        } else if(x == 2) {
          if(l < d) cond = 1;
        }
        int cond2 = 0;
        if(y==0) {
          if(d) cond2 = 1;
        } else if(y==1) {
          cond2 = 2;
        } else {
          cond2 = 2;
        }
        (dp[i+1][j||d<lim][(k+mo[n-1-i]*d)%m][d][cond][cond2] += dp[i][j][k][l][x][y]) %= MOD;
      }
    }
  }

  if(n != 1) {
    REP(i, 2) REP(j, 10) FOR(k, 1, 3) REP(l, 3) {
      if(!dp[n][i][0][j][k][l]) continue;
      // cout << n << "," << i << "," << 0 << "," << j << "," << k << "," << l << " ";
      // cout << dp[n][i][0][j][k][l] << endl;
      (ans -= dp[n][i][0][j][k][l] + MOD) %= MOD;
    }
    REP(i, 9) ans -= (i+1)%m==0;
    ans = (ans%MOD+MOD)%MOD;
  } else {
    REP(i, a[0]-'0') {
      ans -= (i+1)%m==0;
    }
  }

  // aがmの倍数かつジグザグ数ならansに+1する
  bool can = a[0]!=a[1];
  bool flag = a[0]<a[1];
  FOR(i, 2, n) {
    if(flag) {
      if(a[i-1]>a[i]) {
        flag = false;
      } else {
        can = false;
        break;
      }
    } else {
      if(a[i-1]<a[i]) {
        flag = true;
      } else {
        can = false;
        break;
      }
    }
  }
  int now = 0;
  for(int i=n-1; i>=0; --i) now = (now*10 + (a[i]-'0')) % m;
  if(now) can = false;
  if(can) ans++;

  cout << ans%MOD << endl;

  return 0;
}