Official
E - Digit Circus Editorial by en_translator
We can solve the problem using the method called Digit DP (Dynamic Programming).
In the DP, we exceptionally allow leading zeros to treat that all integers have exactly \(N\) digits.
It suffices to maintain the following parameters representing the states of the first \(i\) digits that have been determined:
- the set of digits \(b\) already used
- the remainder \(m\) when divided by \(3\)
- the variable \(l\) representing whether the first \(i\) digits are strictly smaller than or equal to those of \(N\)
Given a state \(dp[i-1][b][m][l]\) and the \((i+1)\)-th digit \(d\), the next state \(dp[i][\cdot][\cdot][\cdot]\) and the transition coefficient can be determined. For more details, refer to the sample code.
As an implementation note, be careful not to regard that the digit 0 has been used when a leading zero was placed.
The time complexity is \(O(2^D D \log N)\), where \(D=10\).
Sample code (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
#include <string>
using std::string;
using std::to_string;
#include <bit>
using std::popcount;
typedef long long int ll;
const ll FOD = 998244353;
string s;
ll dp[505][1 << 10][3][2];
void solve() {
// init dp[0]
for (ll bi = 0; bi < (1<<10); bi++) {
for (ll mi = 0; mi < 3; mi++) {
for (ll li = 0; li < 2; li++) {
dp[0][bi][mi][li] = 0;
}
}
}
dp[0][0][0][0] = 1;
for (ll i = 0; i < s.size(); i++) {
ll si = (s[i] - '0');
// init dp[i+1]
for (ll bi = 0; bi < (1<<10); bi++) {
for (ll mi = 0; mi < 3; mi++) {
for (ll li = 0; li < 2; li++) {
dp[i+1][bi][mi][li] = 0;
}
}
}
// dp[i] -> dp[i+1]
for (ll bi = 0; bi < (1<<10); bi++) {
for (ll mi = 0; mi < 3; mi++) {
// unroll loop for li
for (ll d = 0; d <= 9; d++) {
ll bx = ((bi == 0 && d == 0) ? 0 : (bi | (1LL << d)));
ll mx = (mi * 10 + d) % 3;
// li 0
if (d <= si) {
dp[i+1][bx][mx][(d == si) ? 0 : 1] += dp[i][bi][mi][0];
}
dp[i+1][bx][mx][1] += dp[i][bi][mi][1];
}
}
}
// modulo
for (ll bi = 0; bi < (1<<10); bi++) {
for (ll mi = 0; mi < 3; mi++) {
for (ll li = 0; li < 2; li++) {
dp[i+1][bi][mi][li] %= FOD;
}
}
}
}
// dp[n] -> ans
ll ans = 0;
for (ll bi = 1; bi < (1<<10); bi++) {
for (ll mi = 0; mi < 3; mi++) {
for (ll li = 0; li < 2; li++) {
ll cond = 0;
if (popcount((uint64_t)bi) == 3) cond++;
if (bi & (1LL << 3)) cond++;
if (mi == 0) cond++;
if (cond == 1) {
ans += dp[s.size()][bi][mi][li];
}
}
}
}
ans %= FOD;
cout << ans << "\n";
}
int main (void) {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
cin >> s;
solve();
return 0;
}