Submission #1770605

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#define stirng string
#define vvi vector<vector<int>>
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int INF = 1e9 + 7;

int main() {
  long long int p;
  string b;
  cin >> p >> b;
  p--;
  stirng a = to_string(p);
  int n, m;
  n = b.size();
  m = a.size();
  int dp[n + 1][2][2] = {0};
  int DP[m + 1][2][2] = {0};
  dp[0][0][0] = 1;
  DP[0][0][0] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int lim = j ? 9 : b[i] - '0';
        rep(d, lim + 1) {
          if (j == 1 || d < lim) {
            if (k == 1 || d == 4 || d == 9) {
              dp[i + 1][1][1] += dp[i][j][k];
            } else {
              dp[i + 1][1][0] += dp[i][j][k];
            }
          } else {
            if (k == 1 || d == 4 || d == 9) {
              dp[i + 1][0][1] += dp[i][j][k];
            } else {
              dp[i + 1][0][0] += dp[i][j][k];
            }
          }
        }
      }
    }
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int lim = j ? 9 : a[i] - '0';
        rep(d, lim + 1) {
          if (j == 1 || d < lim) {
            if (k == 1 || d == 4 || d == 9) {
              DP[i + 1][1][1] += DP[i][j][k];
            } else {
              DP[i + 1][1][0] += DP[i][j][k];
            }
          } else {
            if (k == 1 || d == 4 || d == 9) {
              DP[i + 1][0][1] += DP[i][j][k];
            } else {
              DP[i + 1][0][0] += DP[i][j][k];
            }
          }
        }
      }
    }
  }

  cout << dp[n][0][1] + dp[n][1][1] - (DP[m][0][1] + DP[m][1][1]) << endl;

  return 0;
}

Submission Info

Judge Result