# Digit DP

Hihocoder 1033:

$f(x) = a_0 - a_1 + a_2 - \cdots + (-1)^{n-1} a_{n-1}$. e.g., $f(3214567)=3-2+1-4+5-6+7=4$.

Find $\sum_{x=l}^r [f(x)=k] x$.

#include <bits/stdc++.h>
using namespace std;
const int modn = 1e9 + 7;
const int offset = 200;
typedef long long LL;

int p10[22];
int dp[22][22][2][400], f[22][22][2][400];
int t[22], k;

// save for both limit and unlimited
pair<int, int> dfs(int len, int pos, int limit, int partial_sum) {
// printf("%d %d %d %d\n", len, pos, limit, partial_sum);
int &ret = dp[len][pos][limit][partial_sum + offset];
int &fx = f[len][pos][limit][partial_sum + offset];
if (ret == -1) {
if (pos == 0) {
ret = (partial_sum == k);
fx = 0;
} else {
int upper = limit ? t[pos] : 9;
ret = 0;
for (int digit = upper; digit >= 0; --digit) {
int nlen = len, padd = digit;
if (pos == len && digit == 0) nlen--;
pair<int, int> tmp = dfs(nlen, pos - 1, limit && digit == upper, partial_sum + padd);
ret = (ret + tmp.first) % modn;
fx = (fx + 1LL * digit * p10[pos - 1] % modn * tmp.first % modn + tmp.second) % modn;
}
}
}
return make_pair(ret, fx);
}

int solve(long long x) {
if (x <= 0) return 0;
int cnt = 0;
while (x) {
t[++cnt] = x % 10;
x /= 10;
}
memset(dp, -1, sizeof dp);
memset(f, 0, sizeof f);
p10[0] = 1;
for (int i = 1; i <= 20; ++i)
p10[i] = (1LL * p10[i - 1] * 10) % modn;
pair<int, int> ret = dfs(cnt, cnt, 1, 0);
return ret.second;
}

int main() {
long long a, b;
cin >> a >> b >> k;
cout << (solve(b) - solve(a - 1) + modn) % modn << endl;
}

LL dfs(LL base, LL pos, LL len, LL s, bool limit) {
if (pos == -1) return s ? base : 1;
if (!limit && dp[base][pos][len][s] != -1) return dp[base][pos][len][s];
LL ret = 0;
LL ed = limit ? a[pos] : base - 1;
FOR (i, 0, ed + 1) {
tmp[pos] = i;
if (len == pos)
ret += dfs(base, pos - 1, len - (i == 0), s, limit && i == a[pos]);
else if (s &&pos < (len + 1) / 2)
ret += dfs(base, pos - 1, len, tmp[len - pos] == i, limit && i == a[pos]);
else
ret += dfs(base, pos - 1, len, s, limit && i == a[pos]);
}
if (!limit) dp[base][pos][len][s] = ret;
return ret;
}

LL solve(LL x, LL base) {
LL sz = 0;
while (x) {
a[sz++] = x % base;
x /= base;
}
return dfs(base, sz - 1, sz - 1, 1, true);
}


Metropolitan 2018 J:

int a[20];
LL dp[110][14][110][110];

LL dfs(int base, int pos, int tot, int digitsum, bool limit) {
if (pos == -1) return digitsum == base && tot == 0 ? 1 : 0;
if (!limit && dp[base][pos][tot][digitsum] != -1) return dp[base][pos][tot][digitsum];
LL ret = 0;
int ed = limit ? a[pos] : 9;
FOR(i, 0, ed + 1)
ret += dfs(base, pos - 1, (tot * 10 + i) % base, digitsum + i, limit && i == a[pos]);
if (!limit) dp[base][pos][tot][digitsum] = ret;
// dbg(base, pos, tot, digitsum, ed, limit, ret);
return ret;
}

LL solve(LL x) {
LL sz = 0;
while (x) {
a[sz++] = x % 10;
x /= 10;
}
LL ans = 0;
for (int base = 1; base <= 108; ++base)
ans += dfs(base, sz - 1, 0, 0, true);
return ans;
}