Submission #2619854

---

Source Code Expand

#include <bits/stdc++.h>

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

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

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

string N;
ll dp[MAX_N][2][MAX_N];

ll dfs(ll k = 0, bool tight = true, ll cur = 0) {
    if(k >= N.length()) {
        return cur;
    }

    ll x = N[k] - '0';
    ll r = (tight ? x : 9);

    ll& res = dp[k][(tight ? 1 : 0)][cur];
    if(~res) { return res; }
    res = 0;

    for(ll i = 0; i <= r; ++i) {
        res += dfs(k+1, tight && i == r, (i == 1) ? cur+1 : cur);
        res %= MOD;
    }
    return res;
}

signed main()
{
    cin >> N;
    MINUS(dp);
    printf("%lld\n", dfs());
    return 0;
}

Submission Info

Judge Result