基本的数位dp
#include <cstdio>
#include <cstring>
using namespace std; #define D(x) x const int MAX_DIGIT = ; long long n;
int f[MAX_DIGIT];
long long memoize[MAX_DIGIT][][][]; void to_digits(long long a)
{
for (int i = ; i < MAX_DIGIT; i++)
{
f[i] = a % ;
a /= ;
}
} long long dfs(int digit, bool less, bool contain, bool four)
{
if (digit == -)
{
return contain;
}
if (memoize[digit][less][contain][four] != -)
{
return memoize[digit][less][contain][four];
}
int limit = less ? : f[digit];
long long ret = ;
for (int i = ; i <= limit; i++)
{
if (four && i == )
{
ret += dfs(digit - , less || i < f[digit], true, false);
continue;
}
if (i == )
{
ret += dfs(digit - , less || i < f[digit], contain, true);
continue;
}
ret += dfs(digit - , less || i < f[digit], contain, false);
}
memoize[digit][less][contain][four] = ret;
return ret;
} int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%I64d", &n);
to_digits(n);
memset(memoize, -, sizeof(memoize));
long long ans = dfs(, false, false, false);
printf("%I64d\n", ans);
}
return ;
}