AOJ0570

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

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

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4.   
5. using namespace std;  
6.   
7. const int MOD = 500 + 1;  
8. const int LEN = 500 + 1;  
9. const int LAST = 10;  
10. const int A = 2;  
11. const int P = 2;  
12.   
13. int t[LEN][LAST][MOD][A][P];  
14.   
15. int M;  
16. int lim;  
17. string str;  
18.   
19. const int mod = 10000;  
20.   
21. int rec(int len, int last, int carry, bool a, bool p)  
22. {  
23.   if (len == lim) return carry == 0;  
24.   if (t[len][last][carry][a][p] != -1) return t[len][last][carry][a][p];    
25.   
26.   int sum = 0;  
27.   int b, e;  
28.   if (a) b = last + 1, e = 10;  
29.   else   b = 0,        e = last;  
30.   
31.   for (int n = b; n < e; ++n) {  
32.     int m = (carry * 10 + n) % M;  
33.     if (p) {        
34.       if (str[len + 1] - '0' >= n) {  
35.         sum += rec(len + 1, n, m, a^1, (str[len + 1] - '0') == n);  
36.       }  
37.     } else sum += rec(len + 1, n, m, a^1, false);  
38.     sum %= mod;  
39.   }  
40.   
41.   return t[len][last][carry][a][p] = sum;  
42. }  
43.   
44. int calc(string s)  
45. {  
46.   fill(&t[0][0][0][0][0], &t[LEN - 1][LAST - 1][MOD - 1][A - 1][P], -1);  
47.   int sum = 0;  
48.   lim = (int)s.size() - 1;  
49.   str = s;  
50.     
51.   for (int i = 1; i <= s[0] - '0'; ++i) {   
52.     if (lim) {  
53.       sum += rec(0, i, i%M, 0, s[0] - '0' == i);  
54.       sum %= mod;  
55.     }  
56.     sum += rec(0, i, i%M, 1, s[0] - '0' == i);  
57.     sum %= mod;  
58.   }  
59.   
60.   for (int i = 1; i <= lim; ++i) {  
61.     for (int j = 1; j < 10; ++j) {  
62.       if (i != lim) {  
63.         sum += rec(i, j, j%M, 0, false);  
64.         sum %= mod;  
65.       }  
66.       sum += rec(i, j, j%M, 1, false);  
67.       sum %= mod;  
68.     }  
69.   }  
70.   
71.   return sum;  
72. }  
73.   
74. string minus1(string s)  
75. {  
76.   if (s.size() == 1) { --s[0]; return s; }  
77.   for (int i = (int)s.size() - 1; i; --i) {  
78.     --s[i];  
79.     if ('0' <= s[i]) break;  
80.     else {  
81.       s[i] = '9';  
82.       --s[i - 1];  
83.     }  
84.   }  
85.   while (s[0] == '0' && s.size()) s = s.substr(1);  
86.   
87.   return s;  
88. }  
89.   
90. int main(int argc, char *argv[])  
91. {  
92.   string u, v;  
93.   while (cin >> u >> v >> M) {  
94.     int y = calc(v);  
95.     int x = calc(minus1(u));  
96.   
97.     cout << (y - x + mod) % mod << endl;  
98.   }  
99.   return 0;  
100. }  

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