AOJ0570

AOJ0570
memo[桁数][最後に使った数][ここまでの余り][増加or減少][与えられた数より小さくなったかどうか]
筆算をする。
[与えられた数より小さくなったかどうか]はつまり、ここまで作った数字のプレフィックスが一致しているかどうか。
D桁目まで一致しているのであれば、次の数字は与えられた数NのD+1桁目以下でなければならない。
この制約があることで、ある数N以下で条件を満たす個数が分かる。
既に一致していない場合は、D+1桁目より大きな数を選んでもよい。

 (y - x + mod) % mod を忘れると答えが負になることがある。これで相当悩んだ。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MOD = 500 + 1;
const int LEN = 500 + 1;
const int LAST = 10;
const int A = 2;
const int P = 2;

int t[LEN][LAST][MOD][A][P];

int M;
int lim;
string str;

const int mod = 10000;

int rec(int len, int last, int carry, bool a, bool p)
{
  if (len == lim) return carry == 0;
  if (t[len][last][carry][a][p] != -1) return t[len][last][carry][a][p];  

  int sum = 0;
  int b, e;
  if (a) b = last + 1, e = 10;
  else   b = 0,        e = last;

  for (int n = b; n < e; ++n) {
    int m = (carry * 10 + n) % M;
    if (p) {      
      if (str[len + 1] - '0' >= n) {
        sum += rec(len + 1, n, m, a^1, (str[len + 1] - '0') == n);
      }
    } else sum += rec(len + 1, n, m, a^1, false);
    sum %= mod;
  }

  return t[len][last][carry][a][p] = sum;
}

int calc(string s)
{
  fill(&t[0][0][0][0][0], &t[LEN - 1][LAST - 1][MOD - 1][A - 1][P], -1);
  int sum = 0;
  lim = (int)s.size() - 1;
  str = s;
  
  for (int i = 1; i <= s[0] - '0'; ++i) { 
    if (lim) {
      sum += rec(0, i, i%M, 0, s[0] - '0' == i);
      sum %= mod;
    }
    sum += rec(0, i, i%M, 1, s[0] - '0' == i);
    sum %= mod;
  }

  for (int i = 1; i <= lim; ++i) {
    for (int j = 1; j < 10; ++j) {
      if (i != lim) {
        sum += rec(i, j, j%M, 0, false);
        sum %= mod;
      }
      sum += rec(i, j, j%M, 1, false);
      sum %= mod;
    }
  }

  return sum;
}

string minus1(string s)
{
  if (s.size() == 1) { --s[0]; return s; }
  for (int i = (int)s.size() - 1; i; --i) {
    --s[i];
    if ('0' <= s[i]) break;
    else {
      s[i] = '9';
      --s[i - 1];
    }
  }
  while (s[0] == '0' && s.size()) s = s.substr(1);

  return s;
}

int main(int argc, char *argv[])
{
  string u, v;
  while (cin >> u >> v >> M) {
    int y = calc(v);
    int x = calc(minus1(u));

    cout << (y - x + mod) % mod << endl;
  }
  return 0;
}